LA 6893 The Big Painting（矩阵Hash）

题意：

给出一个小矩阵和大矩阵，在大矩阵中能找到相同的小矩阵。

思路：

矩阵Hash，先对小矩阵计算出它的Hash值，然后处理大矩阵，计算出每个子矩阵的Hash值，然后和小矩阵的Hash值比较是否相等。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<string>
 6 #include<vector>
 7 #include<queue>
 8 #include<cmath>
 9 using namespace std;
10 
11 typedef unsigned long long ULL;
12 
13 const ULL Base1 = 2007;
14 const ULL Base2 = 2009;
15 
16 int test,n,m,x,y;
17 ULL ans;
18 char s[2005][2005],a[2005][2005];
19 ULL hash;
20 ULL temp[2005][2005],Temp[2005][2005];
21 
22 ULL Gethash()
23 {
24     ULL c,sum = 0;
25     for(int i = 0; i < x; ++i)
26     {
27         c = 0;
28         for(int j = 0; j < y; ++j)
29         {
30             c = c*Base1 + a[i][j];
31         }
32         sum = sum * Base2 + c;
33     }
34     return sum;
35 }
36 
37 //计算出每个子矩阵的Hash值，并比较Hash值是否相等
38 void GetAns()
39 {
40     ULL t=1, c;
41     for(int i = 0; i < y; ++i) t *= Base1;
42     for(int i = 0; i < n; ++i)
43     {
44         c = 0;
45         for(int j = 0; j < y; ++j) c = c*Base1 + s[i][j];
46         temp[i][y-1] = c;
47         for(int j = y; j < m; ++j)
48         {
49             temp[i][j]=temp[i][j-1]*Base1-s[i][j-y]*t+s[i][j];
50         }
51     }
52 
53     t = 1;
54     for(int i = 0; i < x; ++i) t *= Base2;
55     for(int i = y-1; i < m; ++i)
56     {
57         c = 0;
58         for(int j = 0; j < x; ++j) c = c*Base2 + temp[j][i];
59         Temp[x-1][i] = c;
60         if(c == hash) ans++;
61         for(int j = x; j < n; ++j)
62         {
63             Temp[j][i] = Temp[j-1][i]*Base2 - temp[j-x][i] * t + temp[j][i];
64             if(Temp[j][i]== hash) ans++;
65         }
66     }
67 }
68 
69 int main()
70 {
71     //freopen("D:\input.txt","r",stdin);
72     while(scanf("%d%d%d%d",&x,&y,&n,&m)!= EOF)
73     {
74         for(int i = 0; i < x; ++i) scanf("%s",a[i]);
75         for(int i = 0; i < n; ++i) scanf("%s",s[i]);
76         hash = Gethash();
77         ans = 0;
78         GetAns();
79         printf("%llu
",ans);
80     }
81     return 0;
82 }