首页 > 代码库 > uva 11019 - Matrix Matcher(AC自动机)
uva 11019 - Matrix Matcher(AC自动机)
题目链接:uva 11019 - Matrix Matcher
题目大意:给出一个n?m的字符矩阵T,要求找出给定r?c的字符矩阵P在T中出现的次数。
解题思路:对P矩阵中的每一行做一个字符串,形成一个字符串集合。构建AC自动机,然后对T矩阵中的每一行进行一次查找,对应出现在该字符串中的子串对应位置+1,如果有一个位置上r次匹配,那么就存在一个匹配矩阵。
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 1005;
const int maxl = 10005;
const int sigma_size = 127;
char s[maxn][maxn];
int N, M, R, C;
struct Aho_Corasick {
int sz;
int ac[maxl][sigma_size];
int vn[maxl], val[maxl][105];
int fail[maxl], last[maxl];
int cnt[maxn][maxn];
void init ();
int idx (char ch);
void insert (int x, char* str);
void get_fail ();
void find (int id, int c, char *str);
void count_ans(int x, int y, int u);
}ac_map;
void init () {
char word[105];
scanf("%d%d", &N, &M);
for (int i = 1; i <= N; i++)
scanf("%s", s[i]);
ac_map.init();
scanf("%d%d", &R, &C);
for (int i = 1; i <= R; i++) {
scanf("%s", word);
ac_map.insert(i, word);
}
ac_map.get_fail();
}
int solve () {
for (int i = 1; i <= N; i++)
ac_map.find(i, C, s[i]);
int ret = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if (ac_map.cnt[i][j] == R)
ret++;
return ret;
}
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
init();
printf("%d\n", solve());
}
return 0;
}
void Aho_Corasick::init () {
sz = 1;
vn[0] = 0;
memset(ac[0], 0, sizeof(ac[0]));
memset(cnt, 0, sizeof(cnt));
}
int Aho_Corasick::idx (char ch) {
return ch;
}
void Aho_Corasick::insert (int x, char* str) {
int n = strlen(str), u = 0;
for (int i = 0; i < n; i++) {
int v = idx(str[i]);
if (ac[u][v] == 0) {
vn[sz] = 0;
memset(ac[sz], 0, sizeof(ac[sz]));
ac[u][v] = sz++;
}
u = ac[u][v];
}
val[u][vn[u]++] = x;
}
void Aho_Corasick::get_fail () {
fail[0] = 0;
queue<int> que;
for (int i = 0; i < sigma_size; i++) {
int u = ac[0][i];
if (u) {
fail[u] = last[u] = 0;
que.push(u);
}
}
while (!que.empty()) {
int r = que.front();
que.pop();
for (int i = 0; i < sigma_size; i++) {
int u = ac[r][i];
if (u == 0) {
ac[r][i] = ac[fail[r]][i];
continue;
}
que.push(u);
int v = fail[r];
while (v && ac[v][i] == 0)
v = fail[v];
fail[u] = ac[v][i];
last[u] = vn[fail[u]] ? fail[u] : last[fail[u]];
}
}
}
void Aho_Corasick::count_ans (int x, int y, int u) {
if (u) {
for (int i = 0; i < vn[u]; i++)
if (x >= val[u][i])
cnt[x - val[u][i]][y]++;
count_ans(x, y, last[u]);
}
}
void Aho_Corasick::find(int x, int y, char* str) {
int n = strlen(str), u = 0;
for (int i = 0; i < n; i++) {
int v = idx(str[i]);
u = ac[u][v];
if (vn[u])
count_ans(x, i - y + 1, u);
else if (last[u])
count_ans(x, i - y + 1, last[u]);
}
}
uva 11019 - Matrix Matcher(AC自动机)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。