二次元hash(Uva 12886)
9472 ワード
http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=88791(テーマ接続)
この問題は大きな行列の中から小さい行列を見つけて、行列でhashすることです.
行列hashを使う前に、私たちはまず次のような遊びを定義します.
hash 1[][]横列のhash値を記録する.
hash 2[][]縦のhahs値を記録します.
hashは、小行列のhash値を表します.
2つのシード定数を定義します.
const ULL seed 1=100000 07;const ULL seed 2=100000 00007;
二つのシードの値は同じではありません.横と縦のshの値が同じになることがあります.したがって、異なるシード値を使用します.orz==
先に小さい行列のhashの値を求めます.
この問題は大きな行列の中から小さい行列を見つけて、行列でhashすることです.
行列hashを使う前に、私たちはまず次のような遊びを定義します.
hash 1[][]横列のhash値を記録する.
hash 2[][]縦のhahs値を記録します.
hashは、小行列のhash値を表します.
2つのシード定数を定義します.
const ULL seed 1=100000 07;const ULL seed 2=100000 00007;
二つのシードの値は同じではありません.横と縦のshの値が同じになることがあります.したがって、異なるシード値を使用します.orz==
先に小さい行列のhashの値を求めます.
1 ULL get_hash()
2 {
3 ULL t=0;
4 for(int i=0;i<x;i++)
5 {
6 ULL cnt=0;
7 for(int j=0;j<y;j++)
8 cnt=cnt*seed1+s[i][j];//
9 t=t*seed2+cnt;
10 }
11 return t;
12 }
大きな行列の中から小行列を作成します...コードに会いたいですね#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define maxn 2005
using namespace std;
typedef unsigned long long ULL;
const ULL seed1=10000007;
const ULL seed2=100000007;
char s[maxn][maxn];
char ch[maxn][maxn];
ULL hash1[maxn][maxn];
ULL hash2[maxn][maxn];
ULL hash;
ULL ans;
int x,y,n,m;
ULL get_hash()
{
ULL t=0;
for(int i=0;i<x;i++)
{
ULL cnt=0;
for(int j=0;j<y;j++)
cnt=cnt*seed1+s[i][j];
t=t*seed2+cnt;
}
return t;
}
void count_num()
{
ULL c=1;
for(int i=0;i<y;i++)
c=c*seed1; // hash j-y hash , 。。。
for(int i=0;i<n;i++)
{
ULL cnt=0;
for(int j=0;j<y;j++)
cnt=cnt*seed1+ch[i][j];
hash1[i][y-1]=cnt;
for(int j=y;j<m;j++)
{
hash1[i][j]=hash1[i][j-1]*seed1-ch[i][j-y]*c+ch[i][j];// hash
}
}
c=1;
for(int i=0;i<x;i++)
c=c*seed2;
for(int i=y-1;i<m;i++)
{
ULL a=0;
for(int j=0;j<x;j++)
a=a*seed2+hash1[j][i];// hash = =
hash2[x-1][i]=a;
if(a==hash)
ans++;
for(int j=x;j<n;j++)
{
hash2[j][i]=hash2[j-1][i]*seed2-hash1[j-x][i]*c+hash1[j][i];
if(hash2[j][i]==hash)// ans++
ans++;
}
}
}
int main()
{
while(scanf("%d %d %d %d",&x,&y,&n,&m)!=EOF)
{
getchar();
memset(hash1,0,sizeof(hash1));
memset(hash2,0,sizeof(hash2));
for(int i=0;i<x;i++)
scanf("%s",s[i]);
for(int i=0;i<n;i++)
scanf("%s",ch[i]);
hash=get_hash();
ans=0;
count_num();
printf("%llu
",ans);
}
return 0;
}