LA 4670 dominating patterns AC自动机

发布时间:2016-12-11 2:52:06 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"LA 4670 dominating patterns AC自动机",主要涉及到LA 4670 dominating patterns AC自动机方面的内容,对于LA 4670 dominating patterns AC自动机感兴趣的同学可以参考一下。

题意:有n个模板串,给出一个文本串T,求哪个模板串出现的次数最多,注意可能有重复模板串,因为要用到map来标记 做了几天自动机,照着模板来,到现在基本理解,真是满眼泪…… 这道题算是比较典型的自动机了(基本上就是裸题了吖QvQ),主要即判重,利用map来好方便 要判重是因为,比如重复输入 aba aba 那么在第一次插入的时候,val[最后一个a的节点]=1 在第二次插入时,val[最后一个a的节点]=2 这样的话,第二个就把第一个给覆盖了,在统计时 void print(int j) { if(j) { cnt[val[j]]++; print(last[j]); } } 就只会有cnt[2]++了 然后在最后比较时 for(int i=1;i<=n;i++) if(ac.cnt[ms[string(P[i])]]==best) printf("%s\n", P[i]);没有了ms这个映射,i=1时,就没有了,最后只可能会输出第2个aba 因此要记得用map来标记一下 #include<string> #include<cstring> #include<queue> #include<cstdio> #include<iostream> #include<map> #include<string> using namespace std; const int maxnode=1000010; const int sigma_size=26; char T[maxnode], P[155][80]; map<string, int>ms;//用来标记重复 typedef struct AC_automate { int ch[maxnode][sigma_size]; int val[maxnode]; int last[maxnode], f[maxnode];//标记上一个的节点,失配函数 int cnt[maxnode]; int sz; void init() { sz=1; memset(ch[0], 0, sizeof(ch[0])); memset(cnt, 0, sizeof(cnt)); //memset(last, 0, sizeof(last)); //memset(f, 0, sizeof(f)); val[0]=0; ms.clear(); } 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])); ch[u][c]=sz++; val[sz]=0; } u=ch[u][c]; } val[u]=v; ms[string(s)]=v; } void print(int j) { if(j) { cnt[val[j]]++; print(last[j]); } } void find(char* T) { int n=strlen(T); int j=0; for(int i=0;i<n;i++) { int c=idx(T[i]); j=ch[j][c]; if(val[j])print(j); else if(last[j])print(last[j]); } } 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);last[u]=0;} } //按BFS顺序计算失配函数 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]; last[u]=val[f[u]]?val[f[u]]:last[f[u]]; } } } }AhoCorasick_Automata; AhoCorasick_Automata ac; int main() { int n; while(~scanf("%d", &n), n) { ac.init(); for(int i=1;i<=n;i++) { scanf("%s", P[i]); ac.insert(P[i], i); } ac.getFail(); scanf("%s", T); ac.find(T); int best=-1; for(int i=1;i<=n;i++) if(ac.cnt[i]>best)best=ac.cnt[i]; printf("%d\n", best); for(int i=1;i<=n;i++) if(ac.cnt[ms[string(P[i])]]==best) printf("%s\n", P[i]); } return 0; }

上一篇:java基础 IO/线程/GUI,装饰模式
下一篇:国内公有云对比(1.6)- 功能篇总结

相关文章

相关评论