题目： 传送门
题意： 给你一个 n * m 的文本串 T， 再给你一个 r * c 的模式串 S；
问模式串 S 在文本串 T 中出现了多少次。
解：
法一： AC自动机 （正解） 670ms
把模式串的每一行当成一个字符串， 建一个AC自动机。
然后设cnt[ x ][ y ] 表示文本串中，以 (x, y) 这个点为矩阵右上角的点，且矩阵大小为 r * c的矩阵与模式串匹配了多少行。
那最终统计答案的时候， 只需要 o(n * m) 枚举所有点，记录那些 cnt[ x ][ y ] == n 的点 的个数。 就是答案。
那我们建完AC自动机后， 就可以枚举文本串的每一行，让其去跑 建成的AC自动机， 记录匹配情况即可。
文本串的第 x 行和 模式串的 第 i 行匹配， 则， cnt[ x - i + 1][ y ] ++；
我的代码里有一个 nx[ ] 数组， 这个数组的作用是。
若模式串中， 存在多行字符是完全相等的情况， 则你文本串和当前字符串匹配，可能有多种情况。
比如，你模式串的第3行和第5行是完全相等的， 那么， 你要是文本串匹配到了模式串的第3行，那么你也同样匹配到了第5行。
所以，增加nx[]数组来存，同一字符串的不同编号。
#include <bits/stdc++.h> #define LL long long #define rep(i, j, k) for(int i = j; i <= k; i++) #define dep(i, j, k) for(int i = k; i >= j; i--) #define mem(i, j) memset(i, j, sizeof(i)) using namespace std; const int N = 1e3 + 5, M = 1e4 + 5; struct Trie { int ch[M][26], val[M], Fail[M], tot, nx[M], last[M], cnt[N][N]; void init() { mem(ch[0], 0); val[0] = 0; tot = 1; last[0] = 0; mem(cnt, 0); mem(nx, 0); } int get(char Q) { return Q - 'a'; } void join(char s[], int pos) { int now = 0; int len = strlen(s); rep(i, 0, len - 1) { int id = get(s[i]); if(!ch[now][id]) { mem(ch[tot], 0); val[tot] = 0; last[tot] = 0; ch[now][id] = tot++; } now = ch[now][id]; } nx[pos] = val[now]; val[now] = pos; } void getFail() { queue<int> Q; while(!Q.empty()) Q.pop(); rep(i, 0, 25) { if(ch[0][i]) { Q.push(ch[0][i]); Fail[ch[0][i]] = 0; last[ch[0][i]] = 0; } } while(!Q.empty()) { int now = Q.front(); Q.pop(); rep(i, 0, 25) { int u = ch[now][i]; if(!ch[now][i]) ch[now][i] = ch[Fail[now]][i]; else { Q.push(ch[now][i]); Fail[u] = ch[Fail[now]][i]; last[u] = val[Fail[u]] ? Fail[u] : last[Fail[u]]; } } } } void add_ans(int x, int y, int u) { if(u) { if(x - val[u] + 1 >= 0) { cnt[x - val[u] + 1][y]++; } int tmp = val[u]; while(nx[tmp]) { tmp = nx[tmp]; if(x - tmp + 1 >= 0) cnt[x - tmp + 1][y]++; } add_ans(x, y, last[u]); } } void print(char s[], int x) { int len = strlen(s + 1); int now = 0; rep(i, 1, len) { int id = get(s[i]); now = ch[now][id]; if(val[now]) { add_ans(x, i, now); } else if(last[now]) { add_ans(x, i, last[now]); } } } }; Trie AC; char s[1001][1001], ss[101]; int main() { int _; scanf("%d", &_); while(_--) { AC.init(); int n, m; scanf("%d %d", &n, &m); rep(i, 1, n) scanf("%s", s[i] + 1); int r, c; scanf("%d %d", &r, &c); rep(i, 1, r) { scanf("%s", ss); AC.join(ss, i); } AC.getFail(); ///建AC自动机 rep(i, 1, n) { /// 对文本串每一行跑AC自动机，记录匹配情况 AC.print(s[i], i); } int ans = 0; rep(i, 1, n) rep(j, 1, m) { if(AC.cnt[i][j] == r) ans++; } printf("%d\n", ans); } return 0; }
法二： 二维Hash 40ms
参考： 博客
#include <bits/stdc++.h> #define LL long long #define ULL unsigned long long #define rep(i, j, k) for(int i = j; i <= k; i++) #define dep(i, j, k) for(int i = k; i >= j; i--) #define mem(i, j) memset(i, j, sizeof(i)) using namespace std; const int N = 1e3 + 5; const unsigned int hash1 = 1e9 + 7, hash2 = 1e9 + 9; char a[N][N], b[105][105]; unsigned int p1[N], p2[N]; unsigned int hs[N][N]; void init() { p1[0] = 1; p2[0] = 1; rep(i, 1, N - 1) p1[i] = p1[i - 1] * hash1, p2[i] = p2[i - 1]* hash2; } int main() { int _; scanf("%d", &_); init(); while(_--) { int n, m; scanf("%d %d", &n, &m); rep(i, 1, n) scanf("%s", a[i] + 1); int x, y; scanf("%d %d", &x, &y); rep(i, 1, x) scanf("%s", b[i] + 1); rep(i, 1, n) rep(j, 1, m) { /// 预处理n * m矩阵的二维前缀和。（三个方向的前缀和，） hs[i][j] = hs[i - 1][j - 1] * hash1 * hash2 + (hs[i - 1][j] - hs[i - 1][j - 1] * hash2) * hash1 + (hs[i][j - 1] - hs[i - 1][j - 1] * hash1) * hash2 + a[i][j]; } unsigned int S = 0, C; rep(i, 1, x) rep(j, 1, y) { ///算模式串的hash值 S += b[i][j] * p1[x - i] * p2[y - j]; } int ans = 0; rep(i, x, n) rep(j, y, m) { ///枚举文本串所有x*y矩阵，o(1)算出它们的hash值 C = hs[i][j] - hs[i - x][j - y] * p1[x] * p2[y] - (hs[i][j - y] - hs[i - x][j - y] * p1[x]) * p2[y] - (hs[i - x][j] - hs[i - x][j - y] * p2[y]) * p1[x]; if(S == C) ans++; } printf("%d\n", ans); } return 0; }