我好菜啊

AC自動機都不會

AC自動機可以干什么：

用一個模板串匹配多個子串。

這便讓AC自動機可以干許多KMP和Tri樹不能干的事。

AC自動機的構造

首先建立一顆Trie樹。

其次利用KMP的思想（Trie樹上明顯有許多重復的子路徑）

建立一條Fail邊

使得這些子路徑沒有白跑。

#include<bits/stdc++.h> using namespace std; const int N=1e6+100; struct Results{int num;int pos; }Ans[N]; string s[N]; bool operator < (Results A,Results B){return A.num>B.num||(A.num==B.num&&A.pos<B.pos); } struct A_C_Automation{struct Node{int fail;int end;int vis[28]; }AC[N];int cnt;inline void Clear(int p){memset(AC[p].vis,0,sizeof(AC[p].vis));AC[p].fail=0;AC[p].end=0;}inline void Build(string S,int Id){ // cout<<"We _ in"<<'\n';int now=0;//=AC[0].vis[S[0]-'a'];int R=S.length();for(int i=0;i<R;i++){ // cout<<" id = "<<i<<'\n';if(!AC[now].vis[S[i]-'a']){cnt++;AC[now].vis[S[i]-'a']=cnt;Clear(cnt);}now=AC[now].vis[S[i]-'a'];} // cout<<Id<<" Id "<<'\n';AC[now].end=Id;}inline void Get_Fail(){queue<int> Q;for(int i=0;i<27;i++){if(AC[0].vis[i]){AC[AC[0].vis[i]].fail=0;Q.push(AC[0].vis[i]);}}while(!Q.empty()){int u=Q.front();Q.pop();for(int i=0;i<27;i++){if(AC[u].vis[i]){AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i];Q.push(AC[u].vis[i]);}else AC[u].vis[i]=AC[AC[u].fail].vis[i];}}}inline void Query(string S){int R=S.length();int now=0;int ans=0;for(int i=0;i<R;i++){now=AC[now].vis[S[i]-'a'];for(int t=now;t;t=AC[t].fail)Ans[AC[t].end].num++;}} }ACM; int main(){ios::sync_with_stdio(false); // freopen("AC_AUTO.in","r",stdin); // int T; // scanf("%d",&T);while(233){ACM.Clear(0);int n;cin>>n;if(n==0)break;ACM.cnt=0; // cout<<n<<'\n'; // scanf("%d",&n); // cout<<"here"<<'\n';for(int i=1;i<=n;i++){cin>>s[i]; // cout<<"hello "<<'\n';Ans[i].num=0;Ans[i].pos=i;ACM.Build(s[i],i);} // cout<<"here"<<'\n';ACM.AC[0].fail=0;ACM.Get_Fail();string Key;cin>>Key;ACM.Query(Key);sort(&Ans[1],&Ans[n+1]); // for(int i=1;i<=n;i++){ // cout<<Ans[i].num<<" "; // }cout<<Ans[1].num<<'\n';cout<<s[Ans[1].pos]<<'\n';for(int i=2;i<=n;i++){if(Ans[i-1].num==Ans[i].num){cout<<s[Ans[i].pos]<<'\n';}else break;} // cout<<'\n'; // cout<<"end one "<<'\n';}return 0; }

?

轉載于:https://www.cnblogs.com/Leo-JAM/p/10079195.html

總結

以上是生活随笔為你收集整理的省选专练（学习）AC自动机的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。