POJ.3690 Constellations

1.Problem
http://poj.org/problem?id=3690

2.Idea
Rolling Hash D2

3.Source Code

 typedef unsigned long long ull;  
 int N, M, T, P, Q;  
 char field[1100][1100];  
 char patterns[110][1100][1100];  
 ull Hash[1100][1100], tmp[1100][1100];  
 void compute_hash(char a[1100][1100], int n, int m)  
 {  
      const ull B1 = 9973;  
      const ull B2 = 1000000007;  
      ull t1 = 1;  
      for (int j = 0; j < Q; j++) t1 *= B1;  
      for (int i = 0; i < n; i++) {  
           ull e = 0;  
           for (int j = 0; j < Q; j++) {  
                e = e * B1 + a[i][j];  
           }  
           for (int j = 0; j + Q <= m; j++) {  
                tmp[i][j] = e;  
                if (j + Q < m) e = e * B1 - t1 * a[i][j] + a[i][j + Q];  
           }  
      }  
      ull t2 = 1;  
      for (int i = 0; i < P; i++) t2 *= B2;  
      for (int j = 0; j + Q <= m; j++) {  
           ull e = 0;  
           for (int i = 0; i < P; i++) {  
                e = e * B2 + tmp[i][j];  
           }  
           for (int i = 0; i + P <= n; i++) {  
                Hash[i][j] = e;  
                if (i + P < n) e = e * B2 - t2 * tmp[i][j] + tmp[i + P][j];  
           }  
      }  
 }  
 void solve()  
 {  
      int cnt = 0;  
      while (true) {  
           scanf("%d%d%d%d%d", &N, &M, &T, &P, &Q);  
           if (N + M + T + P + Q == 0) break;  
           cnt++;  
           for (int i = 0; i < N; ++i) {  
                scanf("%s", field[i]);  
           }  
           for (int t = 0; t < T; ++t) {  
                for (int i = 0; i < P; ++i) {  
                     scanf("%s", patterns[t][i]);  
                }  
           }  
           multiset<ull> unseen;  
           for (int k = 0; k < T; k++) {  
                compute_hash(patterns[k], P, Q);  
                unseen.insert(Hash[0][0]);  
           }  
           compute_hash(field, N, M);  
           for (int i = 0; i + P <= N; i++) {  
                for (int j = 0; j + Q <= M; j++) {  
                     unseen.erase(Hash[i][j]);  
                }  
           }  
           printf("Case %d: %d\n", cnt, T - unseen.size());  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }