題目來源：UVa 11019 Matrix Matcher
題意：輸入2個字符矩陣 求第二個字符矩陣在第一個字符矩陣中出現的次數
思路：見大白書218頁
#include#include #include #include using namespace std; const int maxn = 1010; const int maxm = 110; char a[maxn][maxn]; char b[maxm][maxm]; int cnt[maxn][maxn]; int n, m, x, y; const int maxnode = 1000*1000+100; const int size = 26; int val[maxnode]; int ch[maxnode][size]; int f[maxnode]; int last[maxnode]; int sz; vector G[maxnode]; void init() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); memset(cnt, 0, sizeof(cnt)); val[0] = 0; last[0] = 0; G[0].clear(); memset(f, 0, sizeof(f)); } void insert(char *s, int v) { int u = 0; for(int i = 0; i < y; i++) { int c = s[i] - 'a'; if(!ch[u][c]) { memset(ch[sz], 0, sizeof(ch[sz])); val[sz] = 0; G[sz].clear(); ch[u][c] = sz++; } u = ch[u][c]; } val[u]++; G[u].push_back(v); } void getFail() { queue Q; f[0] = 0; for(int c = 0; c < size; c++) { int u = ch[0][c]; if(u) { f[u] = 0; Q.push(u); } } while(!Q.empty()) { int r = Q.front(); Q.pop(); for(int c = 0; c < size; c++) { int u = ch[r][c]; if(!u) { ch[r][c] = ch[f[r]][c]; continue; } Q.push(u); int v = f[r]; while(v && !ch[v][c]) v = f[v]; f[u] = ch[v][c]; last[u] = val[f[u]] ? f[u] : last[f[u]]; } } } void find() { for(int i = 0; i < n; i++) { int u = 0; for(int j = 0; j < m; j++) { int c = a[i][j] - 'a'; u = ch[u][c]; if(!val[u] && !last[u]) continue; int v = val[u] ? u : last[u]; while(v) { for(int k = 0; k < G[v].size(); k++) { if(i-G[v][k] >= 0) cnt[i-G[v][k]][j-y+1]++; } v = last[v]; } } } int ans = 0; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) if(cnt[i][j] == x) ans++; printf("%d\n", ans); } int main() { int T; scanf("%d", &T); while(T--) { init(); scanf("%d %d", &n, &m); for(int i = 0; i < n; i++) { scanf("%s", a[i]); } scanf("%d %d", &x, &y); for(int i = 0; i < x; i++) { scanf("%s", b[i]); insert(b[i], i); } getFail(); find(); } return 0; } /* 2 1 1 x 1 1 y 3 3 abc bcd cde 2 2 bc cd */
