首页 > 代码库 > UVALive-4670 Dominating Patterns / 洛谷 3796 【模板】AC自动机
UVALive-4670 Dominating Patterns / 洛谷 3796 【模板】AC自动机
https://vjudge.net/problem/UVALive-4670
中文题面：https://www.luogu.org/problem/show?pid=3796
AC自动机模板
注意如果有重复字符串，要输出所有的重复字符串
可以用重复字符串中标号最小的字符串来表示所有的重复字符串
例：
aba
abba
aba
aba出现了2次，
令mp[1]=mp[3]=1
代码实现的话，只需要在insert的最后判断，
如果这个单词节点还没有标记，标记上这个单词的编号
如果有标记，令当前单词的mp等于单词节点的标记
#include<queue>#include<cstdio>#include<cstring>#include<iostream>using namespace std;char s[1001001],ss[161][81];int sum[151],bl[151*81];int trie[151*81][27],tot;int len,root,id;int f[151*81];int mp[151];queue<int>q;struct AhoCorasickAutomata{ void insert(int j) { len=strlen(ss[j]); root=1; for(int i=0;i<len;i++) { id=ss[j][i]-‘a‘; if(!trie[root][id]) { trie[root][id]=++tot; bl[tot]=0; memset(trie[tot],0,sizeof(trie[tot])); } root=trie[root][id]; } if(!bl[root]) bl[root]=j; mp[j]=bl[root]; } void getfail() { memset(f,0,sizeof(f)); for(int i=0;i<26;i++) trie[0][i]=1; q.push(1); int now,j; while(!q.empty()) { now=q.front();q.pop(); for(int i=0;i<26;i++) { if(!trie[now][i]) continue; q.push(trie[now][i]); j=f[now]; while(!trie[j][i]) j=f[j]; f[trie[now][i]]=trie[j][i]; } } } void find() { len=strlen(s); memset(sum,0,sizeof(sum)); root=1; int j; for(int i=0;i<len;i++) { id=s[i]-‘a‘; while(!trie[root][id]) root=f[root]; root=trie[root][id]; j=root; while(j) { sum[bl[j]]++; j=f[j]; } } }};AhoCorasickAutomata AC;int main(){ int n; while(scanf("%d",&n)!=EOF) { if(!n) return 0; tot=1; memset(trie[1],0,sizeof(trie[1])); memset(mp,0,sizeof(mp)); for(int i=1;i<=n;i++) { scanf("%s",ss[i]); AC.insert(i); } AC.getfail(); scanf("%s",s); AC.find(); int maxn=0; for(int i=1;i<=n;i++) maxn=max(maxn,sum[i]); printf("%d\n",maxn); for(int i=1;i<=n;i++) if(sum[mp[i]]==maxn) puts(ss[i]); }}
UVALive-4670 Dominating Patterns / 洛谷 3796 【模板】AC自动机
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。