【AC自动机】洛谷三道模板题

时间：2023-03-08 21:53:57
【AC自动机】洛谷三道模板题

【题目链接】

https://www.luogu.org/problem/P3808

【题意】

给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。

【题解】

不再介绍基础知识了，就是裸的模板题，直接贴上来。

【代码】

 #include<queue>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N = 5e5+;

 const int M = 1e6+;

 queue < int > Q ;

 typedef struct Aho_Corasick_Automaton{

     int Son[N][],End[N],Fail[N],idx;

     void Init(){

         idx =  ;

         while( !Q.empty() ) Q.pop() ;

         memset(Son ,  , sizeof Son );

         memset(End ,  , sizeof End );

         memset(Fail,  , sizeof Fail );

     }

     void Insert(char s[]){

         int p =  ;

         for(int i=;s[i];i++){

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

             if( !Son[p][t] )

                 Son[p][t] = ++idx;

             p = Son[p][t] ;

         }

         End[p] ++ ;

     }

     void Build(){

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

             if( Son[][i] )

                 Fail[Son[][i]] =  ,Q.push(Son[][i]);

         }

         while( !Q.empty() ){

             int u = Q.front() ;

             Q.pop();

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

                 if( Son[u][i] ){

                     Fail[Son[u][i]] = Son[Fail[u]][i] ;

                     Q.push( Son[u][i] );

                 }else{

                     Son[u][i] = Son[Fail[u]][i];

                 }

             }

         }

     }

     void Query(char s[]){

         int p = ,res = ;

         for(int i=;s[i];i++){

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

             p = Son[p][t] ;

             for(int j=p ; j && ~End[j] ; j = Fail[j] ){

                 res += End[j] ;

                 End[j] = - ;

             }

         }

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

     }

 }AC_Machine ;

 AC_Machine AC ;

 char s[M];

 int n;

 int main(){

     scanf("%d",&n);

     //AC.Init();

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

         scanf("%s",s);

         AC.Insert(s);

     }

     AC.Build();

     scanf("%s",s);

     AC.Query(s);

     return ;

 }

AC自动机1

【题目链接】

https://www.luogu.org/problem/P3796

【题意】

有N个由小写字母组成的模式串以及一个文本串T。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串T中出现的次数最多。

和模板题1一样，就是最后结尾的标记加上一些小改动。

【代码】

 // luogu-judger-enable-o2

 #pragma GCC optimize(2)

 #include<queue>

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 const int N = 5e5+1e4;

 const int M = 1e6+;

 char Str[][],s[M];

 int Cnt[N],vis[N],n;

 queue < int > Q ;

 typedef struct Aho_Corasick_Automaton{

     int Son[N][],End[N],Fail[N],idx;

     void Init(){

         idx =  ;

         while( !Q.empty() ) Q.pop() ;

         memset(Cnt ,  , sizeof Cnt );

         memset(vis ,  , sizeof vis );

         memset(Son ,  , sizeof Son );

         memset(End ,  , sizeof End );

         memset(Fail,  , sizeof Fail );

     }

     void Insert(char s[],int Id ){

         int p =  ;

         for(int i=;s[i];i++){

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

             if( !Son[p][t] )

                 Son[p][t] = ++idx;

             p = Son[p][t] ;

         }

         End[p] ++ ;

         vis[p] = Id;

     }

     void Build(){

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

             if( Son[][i] )

                 Fail[Son[][i]] =  ,Q.push(Son[][i]);

         }

         while( !Q.empty() ){

             int u = Q.front() ;

             Q.pop();

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

                 if( Son[u][i] ){

                     Fail[Son[u][i]] = Son[Fail[u]][i] ;

                     Q.push( Son[u][i] );

                 }else{

                     Son[u][i] = Son[Fail[u]][i];

                 }

             }

         }

     }

     void Query(char s[]){

         int p = ,res = ;

         for(int i=;s[i];i++){

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

             p = Son[p][t] ;

             for(int j=p ; j ; j = Fail[j] ){

                 if( End[j] ){

                     Cnt[vis[j]] ++ ;

                 }

             }

         }

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

             res = max( Cnt[i] , res ) ;

         }

         cout << res << endl;

         //printf("%d\n",res);

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

             if( res == Cnt[i] ){

                 cout << Str[i] << endl;

             }

         }

     }

 }AC_Machine ;

 AC_Machine AC ;

 int main(){

     ios_base :: sync_with_stdio(false);

     cin.tie(NULL) , cout.tie(NULL);

     while ( cin >> n ,n ){

         AC.Init();

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

             //scanf("%s",s);

             cin >> Str[i];

             AC.Insert(Str[i],i);

         }

         AC.Build();

         //scanf("%s",s);

         cin >> s ;

         AC.Query(s);

     }

     return ;

 }

AC自动机2

【题目链接】

https://www.luogu.org/problem/P5357

【题意】

给你一个文本串 SS 和 nn 个模式串 T_{1..n}，请你分别求出每个模式串 Ti​ 在 S 中出现的次数。

【题解】

这个题目就非常有意思了，

其实我还没怎么想就去洛谷看题解了，

发现是还是各显神通呀。大家都很厉害，我这里提供三个人的做法。

其实道理都是一样的。

一种是：进行类似于差分累加的过程。

 #include<queue>

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 const int N = 2e5+;

 const int M = 2e6+;

 typedef struct node{

     int son[],fail;

     int& operator [] (int x) {return son[x];}

 }Node;

 Node Trie[N];

 int Q[N],head[N],Next[N],Ans[N],d[N];

 int Head,Tail,n,idx;

 char s[M];

 void Insert(char s[],int Id ){

     int p =  ;

     for(int i=;s[i];i++){

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

         if( !Trie[p][t] )

             Trie[p][t] = ++idx;

         p = Trie[p][t] ;

     }

     Next[Id] = head[p] ;

     head[p] = Id;

 }

 void Build(){

     Head =  , Tail = ;

     for(int i=;i<;i++) if( Trie[][i] ) Q[++Tail] = Trie[][i];

     while( Head <= Tail ){

         int u = Q[Head++] ;

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

             if( Trie[u][i] ){

                 Trie[Trie[u][i]].fail = Trie[Trie[u].fail][i] ;

                 Q[++Tail] = Trie[u][i] ;

             }else{

                 Trie[u][i] = Trie[Trie[u].fail][i];

             }

         }

     }

 }

 void Query(char s[]){

     int p = ,res = ;

     for(int i=;s[i];i++){

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

         p = Trie[p][t] ;

         d[p] ++ ;

     }

     for(int i=idx;i;i--){

         for(int j=head[Q[i]] ; j ; j = Next[j] )    Ans[j] = d[Q[i]];

         d[ Trie[Q[i]].fail ] += d[ Q[i] ];

     }

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

         cout << Ans[i] << endl ;

     }

 }

 int main(){

     ios_base :: sync_with_stdio(false);

     cin.tie(NULL) , cout.tie(NULL);

     cin >> n;

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

         cin >> s;

         Insert(s,i);

     }

     Build();

     cin >> s ;

     Query(s);

     return ;

 }

AC自动机3—差分做法

一种是拓扑排序的做法

 #include<bits/stdc++.h>

 using namespace std;

 const int N = 2e6+;

 typedef struct Node {

     int son[],Fail,End,Cnt;

     void Clear(){

         memset(son,,sizeof son );

         Fail = End = Cnt =  ;

     }

     int & operator [] (int x){ return son[x];}

 }Node ;

 Node Trie[N];

 char s[N];

 int Ans,idx=,n,Head,Tail;

 int Mp[N],vis[N],Ind[N],Q[N];

 void Insert( char s[] , int Id ){

     int p =  ;

     for(int i=;s[i];i++){

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

         if( !Trie[p][t] )

             Trie[p][t] = ++idx ;

         p = Trie[p][t] ;

     }

     if( !Trie[p].End ) Trie[p].End = Id;

     Mp[Id] = Trie[p].End

     ;

 }

 void Build(){

     Head =  , Tail =  ;

     for(int i=;i<;i++){ Trie[][i] =  ; }

     Q[++Tail] =  ;

     while( Head <= Tail ){

         int u = Q[Head++] ;

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

             int To = Trie[u][i] ;

             if( To ){

                 Trie[To].Fail = Trie[Trie[u].Fail][i];

                 Ind[ Trie[To].Fail ] ++ ;

                 Q[++Tail] = Trie[u][i];

             }else{

                 Trie[u][i] = Trie[Trie[u].Fail][i];

             }

         }

     }

 }

 void Topu( ){

     Head =  , Tail =  ;

     for(int i=;i<=idx;i++) if( !Ind[i] ) Q[++Tail] = i;

     while( Head <= Tail ){

         int u = Q[Head++];

         vis[ Trie[u].End ] = Trie[u].Cnt ;

         int To = Trie[u].Fail ;

         Ind[To] -- ;

         Trie[To].Cnt += Trie[u].Cnt;

         if( Ind[To] ==  )

             Q[++Tail] = To ;

     }

 }

 void Query(char s[]){

     int p =  ;

     for(int i=;s[i];i++){

         p = Trie[p][s[i]-'a'];

         Trie[p].Cnt ++ ;

     }

 }

 int main()

 {

     scanf("%d",&n);

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

         scanf("%s",s);

         Insert( s, i );

     }

     Build() ;

     scanf("%s",s);

     Query(s);

     Topu();

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

         printf("%d\n",vis[Mp[i]]);

     }

 }

 /*

 5

 a

 bb

 aa

 abaa

 abaaa

 abaaabaa

 6

 0

 3

 2

 1

 */

AC自动机3—拓扑排序

最后一种是最正宗的做法了，建fail树。

 #include<bits/stdc++.h>

 using namespace std;

 const int N = 2e6+;

 void dfs(int u);

 void Add_edge(int u,int v);

 char s[N];

 int head[N],nxt[N],to[N], cnt ;

 int n,idx=;

 int Trie[N][],fail[N],Match[N],Sz[N];

 int Q[N],Head,Tail;

 void Insert(char s[] ,int Id){

     int p =  ;

     for(int i=;s[i];i++){

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

         if( !Trie[p][t] ){

             Trie[p][t] = ++idx;

         }

         p = Trie[p][t] ;

     }

     Match[Id] = p ;

 }

 void Build(){

     Head =  , Tail =  ;

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

         Trie[][i] =  ;

     Q[++Tail] =  ;

     while( Head <= Tail ){

         int u = Q[Head++] ;

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

             if( Trie[u][i] ){

                 fail[Trie[u][i]] = Trie[fail[u]][i];

                 Q[++Tail] = Trie[u][i];

             }else{

                 Trie[u][i] = Trie[fail[u]][i];

             }

         }

     }

 }

 void Query(char s[]){

     for(int p=,i=;s[i];i++){

         p = Trie[p][s[i]-'a'];

         Sz[p] ++ ;

     }

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

         Add_edge( fail[i] , i );

     }

     dfs(  );

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

         printf("%d\n",Sz[Match[i]]);

     }

 }

 int main()

 {

     scanf("%d",&n);

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

         scanf("%s",s);

         Insert(s,i);

     }

     Build();

     scanf("%s",s);

     Query(s);

     return ;

 }

 void dfs(int u){

     for(int i=head[u];i;i=nxt[i]){

         int v = to[i] ;

         dfs(v);

         Sz[u] += Sz[v];

     }

 }

 void Add_edge(int u,int v){

     nxt[++cnt]= head[u];

     head[u] = cnt ;

     to[cnt] = v ;

 }

 /*

 5

 a

 bb

 aa

 abaa

 abaaa

 abaaabaa

 6

 0

 3

 2

 1

 */

AC自动机3—fail树

相关文章