Matrix Matcher （二维的Hash板子）

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <stdlib.h>
 5 #include <string>
 6 #include <string.h>
 7 #include <math.h>
 8 #include <vector>
 9 #include <queue>
10 #include <stack>
11 #include <map>
12 #include <set>
13 
14 
15 #define INF 0x3f3f3f3f
16 #define LL long long
17 
18 typedef unsigned long long ull;
19 const int maxn = 1e3+10;
20 
21 char a[maxn][maxn],b[maxn][maxn];
22 ull base1 = 233,base2 = 2333;
23 ull ha[maxn][maxn],hb[maxn][maxn];
24 
25 int main() {
26     int T;
27     scanf("%d",&T);
28     while (T--) {
29         int n,m,x,y;
30         scanf("%d%d",&n,&m);
31         for (int i=1;i<=n;i++) {
32             scanf("%s",a[i]+1);
33         }
34         scanf("%d%d",&x,&y);
35         for (int i=1;i<=x;i++) {
36             scanf("%s",b[i]+1);
37         }
38         ull p1 = 1,p2 = 1;
39         for (int i=1;i<=x;i++) {
40             p2 *= base2;
41         }
42         for (int i=1;i<=y;i++) {
43             p1 *= base1;
44         }
45         for (int i=1;i<=x;i++) {
46             for (int j=1;j<=y;j++) {
47                 hb[i][j] = (b[i][j] - 'a') + hb[i][j-1] * base1 + hb[i-1][j] * base2 - hb[i-1][j-1] * base1 * base2;
48             }
49         }
50         int ans = 0;
51         for (int i=1;i<=n;i++) {
52             for (int j=1;j<=m;j++) {
53                 ha[i][j] = (a[i][j] - 'a') + ha[i][j-1] * base1 + ha[i-1][j] * base2 - ha[i-1][j-1] * base1 * base2;
54                 if (i >= x && j >= y && hb[x][y] == ha[i][j] - ha[i-x][j] * p2 - ha[i][j-y] * p1 + ha[i-x][j-y] * p1 * p2) {
55                     ans++;
56                 }
57             }
58         }
59         printf("%d\n",ans);
60     }
61     return 0;
62 }