簡單版

題目鏈接:
https://www.luogu.org/problem/P3808

---

題目大意

$n$個(gè)模式串，一個(gè)文本串，求有多少個(gè)模式串出現(xiàn)在文本串里。

---

解題思路

普通$AC$自動(dòng)機(jī)不解釋。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=1e6+100; int n,ans; char s[N]; struct ACmac{int fail[N],son[N][30],siz[N],cnt;queue<int> q;void Make(char *s){int x=1,len=strlen(s);for(int i=0;i<len;i++){int c=s[i]-'a';if(!son[x][c]){son[x][c]=++cnt;memset(son[cnt],0,sizeof(son[cnt]));}x=son[x][c];}siz[x]++;return;}void Bfs(){for(int i=0;i<26;i++)son[0][i]=1;q.push(1);fail[1]=0;while(!q.empty()){int x=q.front();q.pop();for(int i=0;i<26;i++){if(!son[x][i]) son[x][i]=son[fail[x]][i];else{q.push(son[x][i]);int y=fail[x];fail[son[x][i]]=son[y][i];}}}}void Find(char *s){int x=1,len=strlen(s);for(int i=0;i<len;i++){int c=s[i]-'a',k=son[x][c];while(k>1&&siz[k]){ans+=siz[k];siz[k]=0;k=fail[k];}x=son[x][c];}return;} }Ac; int main() {scanf("%d",&n);Ac.cnt=1;for(int i=0;i<26;i++)Ac.son[0][i]=1,Ac.son[1][i]=0;for(int i=1;i<=n;i++){scanf("%s",s);Ac.Make(s);}Ac.Bfs();scanf("%s",s);Ac.Find(s);printf("%d\n",ans); }

---

復(fù)雜版

題目鏈接:
https://www.luogu.org/problem/P3796

---

題目大意

$n$個(gè)模式串，一個(gè)文本串，求在文本串中出現(xiàn)次數(shù)最多的模式串并輸出

---

解題思路

在末尾結(jié)點(diǎn)維護(hù)一個(gè)當(dāng)前模式串的編號(hào)，然后匹配的時(shí)候?qū)⒋鸢附y(tǒng)計(jì)到那個(gè)編號(hào)里即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=1e6+100; int n; char s[160][90],S[N]; struct ansnode{int w,pos; }ans[N]; struct ACmac{int fail[N],son[N][30],ed[N],cnt;queue<int> q;void Make(char *s,int num){int x=1,len=strlen(s);for(int i=0;i<len;i++){int c=s[i]-'a';if(!son[x][c]){son[x][c]=++cnt;memset(son[cnt],0,sizeof(son[cnt]));}x=son[x][c];}ed[x]=num;return;}void Bfs(){for(int i=0;i<26;i++)son[0][i]=1;q.push(1);fail[1]=0;while(!q.empty()){int x=q.front();q.pop();for(int i=0;i<26;i++){if(!son[x][i]) son[x][i]=son[fail[x]][i];else{q.push(son[x][i]);int y=fail[x];fail[son[x][i]]=son[y][i];}}}}void Find(char *s){int x=1,len=strlen(s);for(int i=0;i<len;i++){int c=s[i]-'a',k=son[x][c];for(;k;k=fail[k])ans[ed[k]].w++;x=son[x][c];}return;} }Ac; bool cMp(ansnode x,ansnode y) {return x.w==y.w?x.pos<y.pos:x.w>y.w;} int main() {while(1){scanf("%d",&n);if(!n) return 0;Ac.cnt=1;memset(Ac.son,0,sizeof(Ac.son));memset(Ac.fail,0,sizeof(Ac.fail));memset(Ac.ed,0,sizeof(Ac.ed));for(int i=0;i<26;i++)Ac.son[0][i]=1,Ac.son[1][i]=0;for(int i=1;i<=n;i++){scanf("%s",s[i]);ans[i].pos=i;ans[i].w=0;Ac.Make(s[i],i);}Ac.Bfs();scanf("%s",S);Ac.Find(S);sort(ans+1,ans+1+n,cMp);printf("%d\n%s\n",ans[1].w,s[ans[1].pos]);for(int i=2;i<=n;i++){if(ans[i].w==ans[i-1].w)printf("%s\n",s[ans[i].pos]);else break;}} }

總結(jié)

以上是生活随笔為你收集整理的P3808,P3796-[模板]AC自动机（简单版/加强版）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。