洛谷 P3796 【模板】AC自动机（加强版）（AC自动机）

题目链接：https://www.luogu.com.cn/problem/P3796

AC自动机：复杂度$O( (N+M)\times L )$，N为模式串个数，L为平均长度，M为文章长度。

insert：

　　构造一个trie，然后标记一下每一个模式串的最后一个，即$vis$。

get_fail：

　　进行在trie上进行BFS，第一层点的失配指针指向根节点；之后的一个节点失配指针指向/他父亲的失配指针/指向的节点中/的儿子具有相同节点的位置。

　　这里有一个小优化：fail是用来寻找失配时走到的位置的，走一个点fail的他的ch[i]一定是没有的。那么可以用这些ch指针直接指向它的fail的ch[i]，可以发现这样操作之后，每个点的ch[i]直接指向了原本沿着失配边不停走的最终结果，这样的话，匹配时每次用ch指针的对象即可，不用一直沿fail边走看看这个点有没有ch[i]了。

query：

　　向下一层循环求解，直到fail不能走了，注意如果j不是终点，那么即ans[0]++，但最终不影响结果，因为统计时从1开始...

AC代码：

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 using namespace std;

 const int N=+;

 const int maxn=;

 int fail[N],ch[N][],vis[N];

 int ans[N];

 string s[maxn];

 int cnt;

 void insert(string s,int v){

     int u=;

     int len=s.length();

     for(int i=;i<len;i++){

         int id=s[i]-'a';

         if(!ch[u][id]) ch[u][id]=++cnt;

         u=ch[u][id];

     }

     vis[u]=v;

 }

 void get_fail(){

     int now=;

     queue<int> q;

     for(int i=;i<;i++){

         if(ch[now][i]){

             q.push(ch[now][i]);

             fail[ch[now][i]]=now;

         }

     }

     while(!q.empty()){

         int u=q.front();

         q.pop();

         for(int i=;i<;i++){

             int v=ch[u][i];

             if(v) fail[v]=ch[fail[u]][i],q.push(v);

             else ch[u][i]=ch[fail[u]][i];//you hua

         }

     }

 }

 void query(string s){

     int now=;

     int len=s.length();

     for(int i=;i<len;i++){

         now=ch[now][s[i]-'a'];

         for(int j=now;j;j=fail[j]) ans[vis[j]]++;

     }

 }

 int main(){

     int n;

     while(scanf("%d",&n)){

         memset(vis,,sizeof(vis));

         memset(ans,,sizeof(ans));

         memset(ch,,sizeof(ch));

         memset(fail,,sizeof(fail));

         if(n==) break;

         for(int i=;i<=n;i++){

             cin>>s[i];

             insert(s[i],i);

         }

         get_fail();

         string str;

         cin>>str;

         query(str);

         int maxx=;

         for(int i=;i<=n;i++) maxx=max(maxx,ans[i]);

         printf("%d\n",maxx);

         for(int i=;i<=n;i++) if(ans[i]==maxx) cout<<s[i]<<endl;

     }

     return ;

 }

AC代码

巴特西

洛谷 P3796 【模板】AC自动机（加强版）（AC自动机）

最新文章

热门文章