poj 3690文字マトリクスマッチング---HASHアルゴリズム

http://poj.org/problem?id=3690
UVAのもう一つもこのような問題があって、LRJのあげるアルゴリズムはACオートマチック----私はまだ書いたことがなくて、今日HASHでこの問題をやりました
考えははっきりしていますが、HASH関数で何度かWAを书き混ぜました...
テキストマトリクスn*m   T個のマッチングマトリクスp*q
考え方:1、各行をqと長いhash値に処理する
2、1で得られたp個のハッシュ値に対して1回のハッシュを計算し、これにより1つのマトリクスを1つのhash値で置き換えた
3、すべてのマッチングマトリクスをmultisetに押し込み、テキストマトリクスの各p*qのサブマトリクスについてマトリクスハッシュ値を算出し、multisetからその値を削除する
4、ans=T-multiset.size()
この問題は文字マトリクスマッチングテンプレートとして使用できます.

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;

#define ls(rt) rt*2
#define rs(rt) rt*2+1
#define ll long long
#define ull unsigned long long
#define rep(i,s,e) for(int i=s;i<e;i++)
#define repe(i,s,e) for(int i=s;i<=e;i++)
#define CL(a,b) memset(a,b,sizeof(a))
#define IN(s) freopen(s,"r",stdin)
#define OUT(s) freopen(s,"w",stdin)

const ull ba1=9973;
const ull ba2=1e8+7;
const int MAXT=1000+10;
const int MAXP=MAXT;//55;

char text[MAXT][MAXT];
char pat[100+5][MAXP][MAXP];

ull ha[MAXT][MAXT],tmp[MAXT][MAXT];
ull base1[MAXT],base2[MAXT];
int N,M,T,P,Q;

void init()
{
    base1[0]=1;
    base2[0]=1;
    for(int i=1;i<MAXT;i++)
    {
        base1[i]=base1[i-1]*ba1;
        base2[i]=base2[i-1]*ba2;
    }
}

void calhash(char mat[][MAXT],int n, int m)
{
    ull e;
    // 
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<Q;j++)
            tmp[i][j]=(j==0)?mat[i][j]:(tmp[i][j-1]*ba1+mat[i][j]);
        for(int j=Q;j<m;j++)
            tmp[i][j]=tmp[i][j-1]*ba1+mat[i][j]-mat[i][j-Q]*base1[Q];
    }
    // 
    for(int j=Q-1;j<m;j++)
    {
        for(int i=0;i<P;i++)
            ha[i][j]=(i==0)?tmp[i][j]:(ha[i-1][j]*ba2+tmp[i][j]);
        for(int i=P;i<n;i++)
            ha[i][j]=ha[i-1][j]*ba2+tmp[i][j]-tmp[i-P][j]*base2[P];
    }
}

int solve()
{
    multiset<ull>app;
    for(int i=0;i<T;i++)
    {
        calhash(pat[i],P,Q);
        app.insert(ha[P-1][Q-1]);
        /*printf("#T--%d# ",i);
        for(int i=0;i<P;i++)
        {
            for(int j=0;j<Q;j++)
                cout << tmp[i][j] << "/" << ha[i][j]  << "   ";
            putchar('
');
        }*/

    }
    calhash(text,N,M);
    for(int i=P-1;i<N;i++)
        for(int j=Q-1;j<M;j++)
            app.erase(ha[i][j]);
    return T-app.size();
}

int main()
{
    //IN("poj3690.txt");
    init();
    int ic=0,ans;
    while(~scanf("%d%d%d%d%d",&N,&M,&T,&P,&Q) && N+M+T+P+Q)
    {
        for(int i=0;i<N;i++)
            scanf("%s",text[i]);
        for(int i=0;i<T;i++)
        {
            for(int j=0;j<P;j++)
                scanf("%s",pat[i][j]);
        }
        printf("Case %d: %d
",++ic,solve());
    }
    return 0;
}