二次元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の値を求めます.
 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; }