UVa 11019 Matrix Matcher AC自动机 二维匹配

发布时间:2016-12-9 8:19:13 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"UVa 11019 Matrix Matcher AC自动机 二维匹配",主要涉及到UVa 11019 Matrix Matcher AC自动机 二维匹配方面的内容,对于UVa 11019 Matrix Matcher AC自动机 二维匹配感兴趣的同学可以参考一下。

先给出n*m的字符矩阵T,再给出一个x*y的模板字符矩阵P,问P在T里出现了多少次 这算是二维的查找了,这挺有意思的,一维的单个模板串匹配用KMP,多个的话升级到树,当一维升级到二级,多个又降回到了单个…… 嗯,回来说下这道题……基本算法已经很明了…… 如果T含P,至少,T包含P的每一行,即至少,必然存在T的某行包括P的某行 因此,先把P的每行构造成自动机,再一行行地判断T,开一个二维数组cnt[row][col]表示,P的右上角出现在P的[row][col]位置 一行行地判断T时,只要找到一个字符串,就更新一下cnt,以下是几个关键点 如何更新cnt: 首先,在更新val[]时,传入的v是其所在行 比如 ab bc 在insert“bc”这个字符串时,更新到结尾'c'时,val[c所在节点]=2,即bc在第二行 那么,在调用print函数时,把T的当前行读进去,比如我们在读T的第2行,当前列也读进去 假设T的当前行是bbc 把2传给print,首先判断(T的当前行-该模板在P的行数)是否越界,2-2>=0,没有越界,当前读到了bbc的第3个(数组下标为2),所以一下cnt[0][2] 即存在一个P,右上角出现在矩阵T的(0, 2)位置 考虑重复模板串: if(val[u]) pre[v]=val[u]; val[u]=v; 那么,第一次读入ab,val为1 第二次读入时,把pre[2]=1; 再把val更新为2 假设还有第三交,pre[3]=2; 再把val更新为3…… 那么在最后统计时,用一个这样的循环 while(preline) { if(row-preline+1>=0) cnt[row-preline+1][i]++; preline=pre[preline]; }就可以把ab出现过的行数全部读出来…… 注: 这题不用last也没关系,因为是个字符矩阵,串长都一样的,不可能存在以某字符为结尾的后缀字符串的 以下是AC代码 #include<cstdio> #include<cstring> #include<queue> #define MAXT 1010 #define MAXP 110 using namespace std; char T[MAXT][MAXT], P[MAXP]; int cnt[MAXT][MAXT]; const int maxnode=100010; const int sigma_size=26; typedef struct acauto { int sz; int f[maxnode]; int ch[maxnode][sigma_size]; int val[maxnode]; int pre[maxnode]; void init() { sz=1; memset(ch[0], 0,sizeof(ch[0])); memset(val, 0, sizeof(val)); memset(pre, 0, sizeof(pre)); //memset(last, 0, sizeof(last)); } int idx(char x){return x-'a';} void insert(char* s, int v) { int u=0, 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])); val[sz]=0; ch[u][c]=sz++; } u=ch[u][c]; } if(val[u]) pre[v]=val[u]; val[u]=v; } void print(int i, int j, int row, int plen) { if(!j)return ; if(row-val[j]+1>=0) cnt[row-val[j]+1][i]++; int preline=pre[val[j]]; while(preline) { if(row-preline+1>=0) cnt[row-preline+1][i]++; preline=pre[preline]; } //print(i, last[j], row, plen); } void find(char *s, int row, int plen) { int n=strlen(s); int j=0; for(int i=0;i<n;i++) { int c=idx(s[i]); j=ch[j][c]; if(val[j])print(i, j, row, plen); //else if(last[j]) print(i, last[j], row, plen); } } void getFail() { queue<int>q; f[0]=0; for(int c=0;c<sigma_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<sigma_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]; int fu=f[u]; //last[u]=val[fu]?f[u]:last[fu]; } } } }AhoCorasick_automata; AhoCorasick_automata ac; int main() { int ncase; scanf("%d", &ncase); while(ncase--) { int n,m; scanf("%d%d", &n, &m); for(int i=0;i<n;i++) { scanf("%s", T[i]); memset(cnt[i], 0, sizeof(cnt[i])); } int x, y; ac.init(); scanf("%d%d", &x, &y); for(int i=1;i<=x;i++) { scanf("%s", P); ac.insert(P, i); } ac.getFail(); for(int i=0;i<n;i++) { ac.find(T[i], i, y); } 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); } return 0; } AC自动机先告一段落了……接下来还有后缀数组,明天开始吧QvQ,感觉论文上写得比较难,先从初开始练手好啦QvQ

上一篇:RSA算法详解与举例
下一篇:keil优化等级设置

相关文章

相关评论