洛谷专题-AC自动机

P3808【模板】AC自动机(简单版)

题意:

本题就是一个最裸的AC自动机模板,问有多少个模式串在文本串中出现,直接套板子即可

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
 using namespace std;
 const int maxn=500010;
 queue<int> q;
 struct AC_Automachine{
     int c[maxn][26],val[maxn],fail[maxn],cnt;
     void ins(char *s){
         int len=strlen(s);int now=0;
         for(int i=0;i<len;i++){
             int v=s[i]-'a';
             if(!c[now][v]) c[now][v]=++cnt;
             now=c[now][v];
         }
        val[now]++;
     }
     void build(){
         for(int i=0;i<26;i++){
             if(c[0][i]){
                 fail[c[0][i]]=0;
                 q.push(c[0][i]);
             } 
         }
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int i=0;i<26;i++){
                if(c[u][i]){
                    fail[c[u][i]]=c[fail[u]][i];
                    q.push(c[u][i]);
                }
                else c[u][i]=c[fail[u]][i];
            }
        }
     }
     int query(char *s){
         int len=strlen(s);
         int now=0,ans=0;
         for(int i=0;i<len;i++){
             now=c[now][s[i]-'a'];
             for(int t=now;t&&~val[t];t=fail[t])
                 ans+=val[t],val[t]=-1;
         }
         return ans;
     }
 }AC;
 int n;
 char p[1000005];
 int main()
 {
     scanf("%d",&n);
     for(int i=1;i<=n;i++) scanf("%s",p),AC.ins(p);
     AC.build();
     scanf("%s",p);
     int ans=AC.query(p);
     cout<<ans<<endl;
     return 0;
 }
View Code

P3796【模板】AC自动机加强版

题意:

这题是询问哪个模式串出现次数最多,输出出现次数与串,有多个则输出多个,做法也不难,开一个ans[i]数组记录模式串i的出现次数,然后求出最大值,再遍历一遍ans数组,输出与最大值相同的下标对应的字符串。还有一点不同的就是,对于insert操作对每个模式串结尾的标记应该改为模式串的编号才能在ans数组中记录

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
 using namespace std; 
 const int maxn=300000;
 string s[160],temp;
 int ans[maxn],n;
 struct AC_Automachine{
     int c[maxn][26],val[maxn],fail[maxn],cnt;
     void init(){
         memset(c,0,sizeof(c));
         memset(ans,0,sizeof(ans));
         memset(val,0,sizeof(val));
         memset(fail,0,sizeof(fail));
         cnt=0;
     }
     void insert(string s,int k){
         int now=0;
         for(int i=0;i<s.length();i++){
             int v=s[i]-'a';
             if(!c[now][v]) c[now][v]=++cnt;
             now=c[now][v];
         }
        val[now]=k;
     }
    void build(){
        queue<int> q;
        for(int i=0;i<26;i++){
            if(c[0][i]){
                fail[c[0][i]]=0;
                q.push(c[0][i]);
            }
        }
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int i=0;i<26;i++){
                if(c[u][i]){
                    fail[c[u][i]]=c[fail[u]][i];
                    q.push(c[u][i]);
                }
                else c[u][i]=c[fail[u]][i];
            }
        }
    }
    void query(string s){
        int now=0;
        for(int i=0;i<s.length();i++){
            now=c[now][s[i]-'a'];
            for(int t=now;t;t=fail[t])
                ans[val[t]]++;
        }
    }
 }AC;
 int main()
 {
     while(scanf("%d",&n)&&n){
         AC.init();
         for(int i=1;i<=n;i++){
             cin>>s[i];
             AC.insert(s[i],i);
         }
         AC.build();
         cin>>temp;
         AC.query(temp);
         int pos=0;
         for(int i=1;i<=n;i++) pos=max(pos,ans[i]);
         cout<<pos<<endl;
         for(int i=1;i<=n;i++) if(ans[i]==pos) cout<<s[i]<<endl; 
     }
 }
View Code

 P2444[POI2000]病毒(Tire图上找环)

题意:

给一些01串,问是否在一个无限长的01串不包含这些串

思路:

可以通过一些逆向思维,那就是假设我们已经构造好了这个串,再在树上匹配

当我们一位一位地匹配的时候,我们会发现,永远都不会跳到某个病毒代码段结尾的位置(以后把这里称作危险节点,因为匹配到此处表明已经出现了某个病毒代码段)

既然这个自动机又像一个图,那我们的问题不就变成了——在AC自动机(trie图)中寻找一个环,并且环上没有任何危险节点,并且还要注意,这个环能被根节点访问到(也就是说从根节点出发能在不经过危险节点的情况下走到到这个环,不然在模拟AC自动机匹配的时候无法到达这个这个环,也就失去了意义)。

找环就属于图论了,DFS一遍,只不过必须从根节点出发(上面提到)。开两个布尔数组,一个记录历史是否访问过,一个记录是否在搜索的栈中。如果搜索过程中发现将要访问的下一个节点之间已经入栈了,就找到解了。不走危险节点,不走历史访问过而已经不在栈中的节点。还注意一下,如果某节点fail指向的是危险节点,那么该节点也是危险节点。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
 using namespace std;
 const int maxn=3e4+10;
 int is[maxn],flag[maxn];
 struct AC_Automachine{
    int c[maxn][2],val[maxn],fail[maxn],cnt;
     void ins(string s){
         int now=0;
         for(int i=0;i<s.size();i++){
             int v=s[i]-'0';
             if(!c[now][v]) c[now][v]=++cnt;
             now=c[now][v];
         }
        val[now]++;        
     }
     void build(){
         queue<int> q;
         if(c[0][0]) q.push(c[0][0]);
         if(c[0][1]) q.push(c[0][1]);
         while(!q.empty()){
             int u=q.front();
             q.pop();
             for(int i=0;i<=1;i++){
                 if(c[u][i]){
                     fail[c[u][i]]=c[fail[u]][i];
                     val[c[u][i]]|=val[fail[c[u][i]]];
                     q.push(c[u][i]);
                 }
                else c[u][i]=c[fail[u]][i];
             }
         }
     }
    void bfs(int x)
     {
         if(is[x]){
             cout<<"TAK"<<endl;
             exit(0);
         }
        if(flag[x]||val[x]) return;
        is[x]=flag[x]=1;
        if(c[x][0]) bfs(c[x][0]);
        if(c[x][1]) bfs(c[x][1]);
        is[x]=0;
     }
 }AC;
 int main()
 {
     string temp;
     int n;
     scanf("%d",&n);
     for(int i=1;i<=n;i++){
         cin>>temp;
         AC.ins(temp);
     }
    AC.build();
    AC.bfs(0);
    printf("NIE
");
    return 0;
 }
View Code
原文地址:https://www.cnblogs.com/overrate-wsj/p/12329507.html