首页 > 代码库 > UVA 11019 - Matrix Matcher(AC自动机)
UVA 11019 - Matrix Matcher(AC自动机)
UVA 11019 - Matrix Matcher
题目链接
题意:给定两个矩阵字符串,要求第二个矩阵在第一个矩阵的出现次数
思路:第二个矩阵按行拆分成自动机,然后用第一个矩阵一行一行去匹配,利用一个rc[N][M]的数组记录下每个左上角对应位置的成功匹配次数,然后找完后,对于每个位置,如果成功匹配次数为x,那么就是成功匹配上了,ans++
代码:
#include <cstdio> #include <cstring> #include <queue> using namespace std; const int MAXNODE = 10005; const int SIGMA_SIZE = 127; const int N = 1005; const int M = 105; struct AutoMac { int ch[MAXNODE][SIGMA_SIZE]; int val[MAXNODE][105]; int vn[MAXNODE]; int next[MAXNODE]; int last[MAXNODE]; int sz; int n, m, x, y; char nm[N][N], xy[M]; int rc[N][N]; void init() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); } int idx(char c) { return c; } void insert(char *s, int v) { int u = 0; int n = strlen(s); for (int i = 0; i < n; i++) { int c = idx(s[i]); if (!ch[u][c]) { memset(ch[sz], 0, sizeof(ch[sz])); memset(val[sz], 0, sizeof(val[sz])); vn[sz] = 0; ch[u][c] = sz++; } u = ch[u][c]; } val[u][vn[u]++] = v; } void getnext() { next[0] = 0; queue<int> Q; for (int c = 0; c < SIGMA_SIZE; c++) { int u = ch[0][c]; if (u) {next[u] = 0; Q.push(u); last[u] = 0;} } while (!Q.empty()) { int r = Q.front(); Q.pop(); for (int c = 0; c < SIGMA_SIZE; c++) { int u = ch[r][c]; if (!u) { ch[r][c] = ch[next[r]][c]; continue; } Q.push(u); int v = next[r]; while (v && !ch[v][c]) v = next[v]; next[u] = ch[v][c]; last[u] = val[next[u]] ? next[u] : last[next[u]]; } } } void print(int r, int c, int j) { if (j) { for (int i = 0; i < vn[j]; i++) { if (r - val[j][i] >= 0) rc[r - val[j][i]][c]++; } print(r, c, last[j]); } } void find(int row) { int u = 0; int n = strlen(nm[row]); for (int i = 0; i < n; i++) { int c = idx(nm[row][i]); u = ch[u][c]; if (val[u]) print(row, i - y + 1, u); else if (last[u]) print(row, i - y + 1, last[u]); } } void solve() { memset(rc, 0, sizeof(rc)); scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%s", nm[i]); scanf("%d%d", &x, &y); for (int i = 1; i <= x; i++) { scanf("%s", xy); insert(xy, i); } getnext(); for (int i = 1; i <= n; i++) find(i); int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (rc[i][j] == x) ans++; } } printf("%d\n", ans); } }; AutoMac gao; int main() { int t; scanf("%d", &t); while (t--) { gao.init(); gao.solve(); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。