就向书上说得那样，如果模式串P的第i行出现在文本串T的第r行第c列，则cnt[r-i][c]++;
还有个很棘手的问题就是模式串中可能会有相同的串，所以用repr[i]来记录第i个模式串P[i]第一次出现的位置。如果repr[i] == i，说明这个模式串之前没有重复过，可以加进自动机里去。有重复的话，把这些重复的模式串组织成一个链表，用next把它们连接起来。
所以在统计cnt的时候，匹配到的模式串可能会作为匹配的第i行，也可能是next[i]行，next[next[i]]行等等。
1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 using namespace std; 5 6 int n, m, x, y, tr; 7 const int maxx = 100 + 10; 8 const int maxn = 1000 + 10; 9 const int maxnode = 10000 + 10; 10 const int sigma_size = 26; 11 char T[maxn][maxn], P[maxx][maxx]; 12 int cnt[maxn][maxn]; 13 int repr[maxx]; 14 int next[maxx]; 15 16 struct AhoCorasickAutomata 17 { 18 int ch[maxnode][sigma_size]; 19 int f[maxnode]; 20 int last[maxnode]; 21 int val[maxnode]; 22 int sz; 23 24 void init() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); } 25 26 inline int idx(char c) { return c - 'a'; } 27 28 void insert(char* s, int v) 29 { 30 int u = 0, n = strlen(s); 31 for(int i = 0; i < n; i++) 32 { 33 int c = idx(s[i]); 34 if(!ch[u][c]) 35 { 36 memset(ch[sz], 0, sizeof(ch[sz])); 37 val[sz] = 0; 38 ch[u][c] = sz++; 39 } 40 u = ch[u][c]; 41 } 42 val[u] = v; 43 } 44 45 void match(int i, int j) 46 { 47 int c = i - y + 1; 48 int pr = repr[val[j] - 1]; 49 while(pr >= 0) 50 { 51 if(tr - pr >= 0) cnt[tr-pr][c]++; 52 pr = next[pr]; 53 } 54 } 55 56 void print(int i, int j) 57 {//在文本串的第i列匹配到单词节点j 58 if(j) 59 { 60 match(i, j); 61 print(i, last[j]); 62 } 63 } 64 65 void find(char* T) 66 { 67 int j = 0, n = strlen(T); 68 for(int i = 0; i < n; i++) 69 { 70 int c = idx(T[i]); 71 while(j && !ch[j][c]) j = f[j]; 72 j = ch[j][c]; 73 if(val[j]) print(i, j); 74 else if(val[last[j]]) print(i, last[j]); 75 } 76 } 77 78 void getFail() 79 { 80 queue<int> q; 81 f[0] = 0; 82 for(int c = 0; c < sigma_size; c++) 83 { 84 int u = ch[0][c]; 85 if(u) { f[u] = 0; last[u] = 0; q.push(u); } 86 } 87 while(!q.empty()) 88 { 89 int r = q.front(); q.pop(); 90 for(int c = 0; c < sigma_size; c++) 91 { 92 int u = ch[r][c]; 93 if(!u) continue; 94 q.push(u); 95 int v = f[r]; 96 while(v && !ch[v][c]) v = f[v]; 97 f[u] = ch[v][c]; 98 last[u] = val[f[u]] ? f[u] : last[f[u]]; 99 } 100 } 101 } 102 }ac; 103 104 int main() 105 { 106 //freopen("in.txt", "r", stdin); 107 108 int test; 109 scanf("%d", &test); 110 while(test--) 111 { 112 scanf("%d%d", &n, &m); 113 for(int i = 0; i < n; i++) scanf("%s", T[i]); 114 scanf("%d%d", &x, &y); 115 ac.init(); 116 for(int i = 0; i < x; i++) 117 { 118 repr[i] = i; 119 next[i] = -1; 120 scanf("%s", P[i]); 121 for(int j = 0; j < i; j++) if(strcmp(P[i], P[j]) == 0) 122 { 123 repr[i] = j; 124 next[i] = next[j]; 125 next[j] = i; 126 break; 127 } 128 if(repr[i] == i) ac.insert(P[i], i+1); 129 } 130 ac.getFail(); 131 memset(cnt, 0, sizeof(cnt)); 132 for(tr = 0; tr < n; tr++) ac.find(T[tr]); 133 134 int ans = 0; 135 for(int i = 0; i < n; i++) 136 for(int j = 0; j < m; j++) 137 if(cnt[i][j] == x) ans++; 138 printf("%d ", ans); 139 } 140 141 return 0; 142 }