2D Rolling Hash
私認為沒什麼參考價值，因為這個算法複雜度太高。
改用其他字串演算法應該會快很多。
因為只有 ‘*’, ‘0’ 兩種字元，就乾脆不 mod 了，
可以搶一點速度。
總之，算法就是先把要搜尋的 NxM 矩陣 Rolling Hash 起來，
然後對每個輸入的 pattern 做 hash ，把它塞進一個 map ，
map 的 Key 存 pattern 的 hash 值， value 用來數次數。
輸入完後，利用 NxM 的矩陣得到的 hash 值，判斷在 map 內的 pattern 是否有出現 ，如果有，累計次數、該 pattern 從 map 移除。
最後輸出累計結果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
// AC, 壓底線？ 2829MS/3000MS, 12380K, G++
#pragma GCC target ("avx")
#pragma GCC optimize ("O3")
#include <cstring>
#include <functional>
#define UT long int
struct RollingHash2D {
#define PB push_back
#define F first
#define S second
enum { MAXN=1002, MAXM=1002 };
static const UT px, py; // X向 hash 的 base, Y向 hash 的 base, mod Prime
UT h[MAXN][MAXM];
UT cacheX[MAXM], cacheY[MAXN];
inline void get_pow(const int n, const int m) { // Hash basis 冪次
// n, 高 / m, 寬
cacheX[0]=1;
cacheY[0]=1;
for (int i=1; i<=n; ++i) {
cacheY[i] = cacheY[i-1]*py;
}
for (int i=1; i<=m; ++i) {
cacheX[i] = cacheX[i-1]*px;
}
}
inline void get_hash(int *s, int n, int m) { // 取得 hash 表
// n, 高 / m, 寬
// 下面要做的事和 2D prefix sum 類似
std::memset(h, 0x00, sizeof(UT)*MAXN*MAXM);
for (int i=1; i<=n; ++i) {
int sum=0;
for (int j=1; j<=m; ++j) {
sum = sum*px + s[(i-1)*m+j-1] + 1; // X 向 hash
h[i][j] = h[i-1][j]*py + sum; // Y 向 hash
}
}
}
inline UT partial_hash(int i, int j, int n, int m) {
// i: row; j: col; n: 高; m: 寬
// 從 s[i][j] 往下看 nxm 大小矩陣，所對應的 hash 值
const UT &pwX = cacheX[m]; // pX^m
const UT &pwY = cacheY[n]; // pY^n
UT result = \
h[i+n][j+m] - (h[i][j+m]*pwY + h[i+n][j]*pwX) + h[i][j]*pwX*pwY;
// 小心 overflow
return result;
}
#undef PB
#undef F
#undef S
};
const UT RollingHash2D::px(3);
const UT RollingHash2D::py(5);
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
RollingHash2D str, pat;
int s[1000010], p[10010];
std::map<UT,int> UTmap;
int main(void) {
using namespace std;
char buffer[3072];
#define RL() (fgets(buffer,3000,stdin))
str.get_pow(66,66);
pat.get_pow(55,55);
int cases=0;
while(RL()!=NULL) {
int N,M,T,P,Q;
sscanf(buffer,"%d %d %d %d %d",&N,&M,&T,&P,&Q);
if (N==0&&M==0&&T==0&&P==0&&Q==0) break;
for (int i=0, k=0; i<N; ++i) {
RL();
for (int j=0; j<M; ++j, ++k) {
s[k] = (buffer[j]=='0'?1:0);
}
}
str.get_hash(s,N,M);
for (int t=0; t<T; ++t) {
RL();
for (int i=0, k=0; i<P; ++i) {
RL();
for (int j=0; j<Q; ++j, ++k) {
p[k] = (buffer[j]=='0'?1:0);
}
}
pat.get_hash(p,P,Q);
++UTmap[pat.partial_hash(0,0,P,Q)];
}
int cnt=0;
// O(W^2 * lgT)
for (int i=0; i+P<=N; ++i) {
for (int j=0; j+Q<=M; ++j) {
map<UT,int>::iterator it = \
UTmap.find(str.partial_hash(i,j,P,Q));
if(it!=UTmap.end()) {
cnt += it->second;
UTmap.erase(it);
}
}
}
++cases;
printf("Case %d: %d\n", cases, cnt);
UTmap.clear();
}
return 0;
}