LA 4670

Type:AC自动机

题意

给你一堆子串和一个主串

问你在主串中出现次数最多的子串有哪些,最后结果按字典序排列

Code

#include<bits/stdc++.h>
using namespace std;

const int maxn=11000;
const int maxm=152;
const int maxt=1e6+6;

int T,N,tot_len;
char str[maxm][80],tot[maxt];

struct AC_AutoMaton{
    static const int sigma_size=26;

    int ch[maxn][sigma_size];

    int f[maxn];

    int cnt[maxn],val[maxn];
    bool vis[maxn][sigma_size];

    int siz,root,max_time;

    vector<string> ans;

    int newNode(){
        for(int i=0;i<sigma_size;++i){
            ch[siz][i]=0;
        }
        for(int i=0;i<sigma_size;++i){
            vis[siz][i]=false;
        }
        f[siz]=val[siz]=0;
        return siz++;
    }

    void init(){
        ans.clear();
        for(int i=0;i<maxn;++i) val[i]=cnt[i]=0;
        siz=0;root=0;max_time=0;
        newNode();
    }

    int ord(char c){
        if(isupper(c))
            c=tolower(c);
        return (int)(c-'a');
    }

    void insert(char *s,int v){
        int u=root,n=strlen(s);
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            if(!ch[u][c]) ch[u][c]=newNode();
            u=ch[u][c];
       }
       val[u]=v;
    }

    void getFail(){
        queue<int> Q;
        Q.push(root);
        while(!Q.empty()){
            int k=Q.front();
            Q.pop();
            for(int c=0;c<sigma_size;++c){
                if(ch[k][c]){
                    f[ch[k][c]]=k?ch[f[k]][c]:0;
                    Q.push(ch[k][c]);
                }
                else ch[k][c]=ch[f[k]][c];
            }
        }
    }

    void Find(char *s){
        int u=0,n=tot_len;
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            ///下面这句加不加都一样
            //while(u && !ch[u][c]) u=f[u];
            u=ch[u][c];

            int p=u;
            //cout<<i<<"  "<<u<<": "<<c<<endl;
            ///while是用来判断子串的.这道题不需要加
            while(p && val[p]){
                if(!vis[p][c]){
                    cnt[val[p]]++;
                    max_time=max(cnt[val[p]],max_time);
                    p=f[p];
                    vis[p][c]=true;
                }
            }
        }
    }

    void print(){
        printf("%d\n",max_time);
        for(int i=1;i<=N;++i){
            if(cnt[i]==max_time){
                ans.push_back(str[i]);
            }
        }
        sort(ans.begin(),ans.end());
        for(int i=0;i<ans.size();++i){
            cout<<ans[i]<<endl;
        }
    }
}aho;

int main(){
    while(~scanf("%d",&N) && N){
        aho.init();
        for(int i=1;i<=N;++i){
            scanf("%s",str[i]);
            aho.insert(str[i],i);
        }
        getchar();
        aho.getFail();
        tot_len=0;
        //scanf("%[^\n]",str);
        gets(tot);
        tot_len=strlen(tot);
        //cout<<tot_len<<endl;
        aho.Find(tot);
        aho.print();
    }
    return 0;
}

HDU 5880

Type: AC自动机

题意

给你N个子串,一个主串,让你过滤掉在主串中出现过的子串.被过滤掉的用*表示

每个子串是由小写字母组成

题解

AC自动机,一开始被两个样例卡住了

1- 子串: abcd bc 主串: abcef 匹配不到 bc
2- 子串: a ab abc abcd 主串: aabcd 匹配不到 abcd

第一种情况是因为当你遍历到abcd这条路径的c节点时,如果因为下一个是f就判断为失配并且不继续向下走,则就无法再匹配到bc.

解决方法,在每次判断到失配的时候,新开一个函数从开始失配的节点 这里是 c ,从这个节点开始找他的失陪路径,知道找到 第一个尾节点 或 根节点 就停止,目标串即为最长被匹配串,不需要再去匹配他的子串了.

第二种情况是因为一开始写代码每次循环时直接将u查找到了根节点,所以如果一个子串前面是另一个串的子串,那么将永远无法匹配到另一个子串.

解决方法,不改动u,借助临时变量来更改u达到查找子串的目的.

Code

#include<bits/stdc++.h>
using namespace std;

const int maxn=1000000+6;

int T,N,tot_len;
char str[maxn],len[maxn];

struct AC_AutoMaton{
    static const int sigma_size=26;

    int ch[maxn][sigma_size];

    int f[maxn];

    int cle[maxn],val[maxn];

    int siz,root;

    int newNode(){
        for(int i=0;i<sigma_size;++i){
            ch[siz][i]=0;
        }
        f[siz]=val[siz]=0;
        return siz++;
    }

    void init(){
        for(int i=0;i<maxn;++i) val[i]=0;

        siz=0;root=0;
        newNode();
    }

    int ord(char c){
        if(isupper(c))
            c=tolower(c);
        return (int)(c-'a');
    }

    void insert(char *s,int v){
        int u=root,n=strlen(s);
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            if(!ch[u][c]) ch[u][c]=newNode();
            u=ch[u][c];
       }
       val[u]=v;
    }

    void getFail(){
        queue<int> Q;
        Q.push(root);
        while(!Q.empty()){
            int k=Q.front();
            Q.pop();
            for(int c=0;c<sigma_size;++c){
                if(ch[k][c]){
                    f[ch[k][c]]=k?ch[f[k]][c]:0;
                    Q.push(ch[k][c]);
                }
                else ch[k][c]=ch[f[k]][c];
            }
        }
    }

    void add(int u,int i){
        while(u){
            if(val[u]){
                int t=len[val[u]];
                for(int r=0;r<t;++r){
                    cle[i-r]=1;
                }
                return;
            }
            u=f[u];
        }
    }

    void Find(char *s){
        int u=0,n=tot_len;
        for(int i=0;i<tot_len;++i) cle[i]=0;
        for(int i=0;i<n;++i){
            if(!isalpha(s[i])){
                u=0;
                continue;
            }
            int c=ord(s[i]);
            ///下面这句加不加都一样
            //while(u && !ch[u][c]) u=f[u];
            u=ch[u][c];
            /*
            int p=u;
            //cout<<i<<"  "<<u<<": "<<c<<endl;
            ///while是用来判断子串的.这道题不需要加
            while(p && val[p]){
                p=f[p];
            }
            */
            add(u,i);
        }
    }

    void print(){
        for(int i=0;i<tot_len;++i){
            if(cle[i]) putchar('*');
            else putchar(str[i]);
        }
        printf("\n");
    }
}aho;

int main(){
    scanf("%d",&T);
    while(T--){
        aho.init();
        scanf("%d",&N);
        for(int i=0;i<N;++i){
            scanf("%s",str);
            aho.insert(str,i+1);
            len[i+1]=strlen(str);
        }
        getchar();
        aho.getFail();
        tot_len=0;
        //scanf("%[^\n]",str);
        gets(str);
        tot_len=strlen(str);
        //cout<<tot_len<<endl;
        aho.Find(str);
        aho.print();
    }
    return 0;
}

HDU 2222

Type: AC自动机

题意

给你几个子串,再给你一个主串,问你有多少个子串在主串中出现过.

输入

T,N,接下来N行输入N个字符串,最后一行输入一个主串.

输出

一个整数,有多少子串可以在主串中被匹配到

题解

注意,每个子串可能是相同的,所以我们不能在尾节点记录子串的下标,而应该记录子串的个数.最后加进去即可

Code

#include<bits/stdc++.h>
using namespace std;

const int maxn=(int)500005;
const int max_tot=(int)1e6+6;

int T,N;
char str[10010][60],tot[max_tot];

struct AC_AutoMaton{
    static const int sigma_size=26;
    static const char first_caractar='a';
    int ch[maxn][sigma_size];
    int f[maxn],last[maxn];
    int cnt[maxn],val[maxn];
    int siz;

    int ans;

    void init(){
        siz=ans=0;
        memset(ch,0,sizeof(ch));
        memset(val,0,sizeof(val));
    }

    int ord(char c){
        return c-first_caractar;
    }

    void insert(char *s){
        int u=0,n=strlen(s);
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            if(!ch[u][c]) ch[u][c]=++siz;
            u=ch[u][c];
       }
       ///表示以第u棵节点为字符串最后一个字符节点的个数
       ///如果想存储该节点代表的是哪个字符串.即存储该字符串的下标
       ///val[u]=v;(v是下标)
       ///但是这样存储就会出现无法统计之前有多少个重复字符串
       ///比如这道题如果输入
       ///3
       ///sha
       ///sha
       ///sha
       ///shashasha
       ///则用第一种方法最后结果是3
       ///但用第二种方法只能匹配一次sha
       val[u]++;
    }
    //Fail树
    void getFail(){
        queue<int> Q;
        f[0]=0;
        ///遍历取出第一个节点所有的前向字符
        for(int c=0;c<sigma_size;++c){
            int u=ch[0][c];
            if(u){
                f[u]=last[u]=0;
                Q.push(u);
            }
        }
        while(!Q.empty()){
            int k=Q.front();
            Q.pop();
            for(int c=0;c<sigma_size;++c){
                int u=ch[k][c];
                if(!u) continue;
                Q.push(u);
                int v=f[k];
                while(v && !ch[v][c]) v=f[v];
                f[u]=ch[v][c];
                last[u]=val[f[u]]?f[u]:last[f[u]];
            }
        }
    }

    ///统计
    void add(int u){
        if(u){
            if(!cnt[u]) ans+=val[u],cnt[u]=1;
            add(last[u]);
        }
    }

    ///多模式匹配
    void Find(char *s){
        int u=0,n=strlen(s);
        memset(cnt,0,sizeof(cnt));
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            while(u && !ch[u][c]) u=f[u];
            u=ch[u][c];
            if(val[u]) add(u);
            else if(last[u]) add(last[u]);
        }
    }
}aho;

int main(){
    scanf("%d",&T);
    while(T--){
        aho.init();
        scanf("%d",&N);
        for(int i=0;i<N;++i){
            scanf("%s",str[i]);
            aho.insert(str[i]);
        }
        aho.getFail();
        scanf("%s",tot);
        aho.Find(tot);
        printf("%d\n",aho.ans);
    }
    return 0;
}

字符串算法

Trie

这个…不想写了

KMP

朴素的对比字符串算法复杂度是O(mn)的.这样一来对两串比较长的字符串就显得略微低效了.

KMP算法的时间复杂度也不过O(m+n)

Next数组

对于KMP而言最重要的莫过于这个Next数组了.

Next数组最大的作用在于当匹配失败时,需要跳转到哪个下标.

构造方法:

Next[i]=max{j | j\<i 且N[1..j]=N[i-j+1..i]}

即Next[i]球的试串P[1..i]的一个最长的前缀P[1..j],这个前缀同时也是他的后缀。当这个前缀找不到的时候,Next[i]=0

例如:

模式串 P = ababc

则Next[4]=2,因为ab不仅是abab的前缀,也是他的后缀.

而Next[5]=0,因为无法找到ababc(P[1..5])的一个前缀同时又是他的后缀.

附上一张图

匹配时逻辑

KMP 在匹配时同时维护两个下标 i 和 j ,表示当前模式串 P 的前 j 个字符与主串 T 在位置 i 前的 j 个字符匹配,即 P[1..j]=T[i-j..i-1]。

当算法尝试对 T[i] 和 P[j+1] 匹配中遇到不相同的字符,就会通过Next数组进行跳跃。

算法实现

Next数组

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+7;
int Next[maxn];
string S,T;//S主串,T子串

void getNext(){
    int k=-1,len=T.length();
    int j=0;
    Next[0]=-1;
    while(j<len){
        //如果有相同前缀
        if(k==-1 || T[j]==T[k]) Next[++j]=++k;
        else k=Next[k];
    }
}

void print(){
    for(int i=0;i<T.length();++i){
        cout<<Next[i]<<" ";
    }
    cout<<endl;
}

int main(){
    while(cin>>T){
        getNext();
        print();
    }
    return 0;
}

几组数据

ababc
Next: -1 0 0 1 2

abcdef
Next: -1 0 0 0 0 0

abcdabce
Next: -1 0 0 0 0 1 2 3

abcabcabc
Next: -1 0 0 0 1 2 3 4 5

abcdabcabcd
Next: -1 0 0 0 0 1 2 3 1 2 3

KMP – 返回第一个匹配的下标

主程

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+7;
int Next[maxn];
string S,T;//S主串,T子串

void getNext(){
    int k=-1,len=T.length();
    int j=0;
    Next[0]=-1;
    while(j<len){
        //如果有相同前缀
        if(k==-1 || T[j]==T[k]) Next[++j]=++k;
        else k=Next[k];
    }
}

void print(){
    for(int i=0;i<T.length();++i){
        cout<<Next[i]<<" ";
    }
    cout<<endl;
}

int KMP_index(){
    int i=0,j=0,slen=S.length(),tlen=T.length();
    getNext();
    while(i<slen && j<tlen){
        if(j==-1 || S[i]==T[j]){
            i++;
            j++;
        }else j=Next[j];
    }
    if(j==tlen) return i-tlen;
    else return -1;
}

int main(){
    while(cin>>S>>T){
        int ans=KMP_index();
        if(ans==-1) cout<<"Failed!"<<endl;
        else cout<<"Succesed!String T was matched in index "<<ans<<"."<<endl;
        print();
    }
    return 0;
}

两组数据

IN[0]: jashdjashdjabababcabcsdas
IN[1]: abcabc
OUT[0]: Succesed!String T was matched in index 15.
OUT[1]: -1 0 0 0 1 2
IN[2]: jashdjashdjabababcabcsdas
IN[3]: abcabcd
OUT[2]: Failed!
OUT[3]: -1 0 0 0 1 2 3

AC-Corasick 自动机

思想是KMP+Trie,在Trie上建立失配指针.

常用于主串匹配多个字符串

尾节点记录字符串下标的AC自动机

优点是可以直接输出字符串.

#include<bits/stdc++.h>
using namespace std;

const int maxn=(int)500005;
const int max_tot=(int)1e6+6;

int T,N;
char str[10010][60],tot[max_tot];

struct AC_AutoMaton{
    static const int sigma_size=26;
    static const char first_caractar='a';
    ///Trie树
    int ch[maxn][sigma_size];
    ///后缀相关数组
    int f[maxn],last[maxn];
    ///个数信息,尾节点记录信息
    int cnt[maxn],val[maxn];
    ///总节点个数
    int siz;

    int all_su;///记录总共有多少不可重复子串

    void init(){
        siz=all_su=0;
        memset(ch,0,sizeof(ch));
        memset(val,0,sizeof(val));
    }

    int ord(char c){
        return c-first_caractar;
    }

    void insert(char *s,int v){
        int u=0,n=strlen(s);
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            if(!ch[u][c]) ch[u][c]=++siz;
            u=ch[u][c];
       }
       ///尾节点记录字符串在str数组的下标
       val[u]=v;
    }

    //Fail树
    void getFail(){
        queue<int> Q;
        f[0]=0;
        ///遍历取出第一个节点所有的前向字符
        for(int c=0;c<sigma_size;++c){
            int u=ch[0][c];
            if(u){
                f[u]=last[u]=0;
                Q.push(u);
            }
        }
        while(!Q.empty()){
            int k=Q.front();
            Q.pop();
            for(int c=0;c<sigma_size;++c){
                int u=ch[k][c];
                if(!u) continue;
                Q.push(u);
                int v=f[k];
                while(v && !ch[v][c]) v=f[v];
                f[u]=ch[v][c];
                last[u]=val[f[u]]?f[u]:last[f[u]];
            }
        }
    }

    ///统计
    void add(int u){
        for(;u;u=last[u]){
            if(!cnt[val[u]]) all_su++;
            printf("\n%s\n",str[val[u]-1]);
            cnt[val[u]]++;
        }
    }

    ///多模式匹配
    void Find(char *s){
        int u=0,n=strlen(s);
        memset(cnt,0,sizeof(cnt));
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            while(u && !ch[u][c]) u=f[u];
            u=ch[u][c];
            if(val[u]) add(u);
            else if(last[u]) add(last[u]);
        }
    }
}aho;

int main(){
    scanf("%d",&T);
    while(T--){
        aho.init();
        scanf("%d",&N);
        for(int i=0;i<N;++i){
            scanf("%s",str[i]);
            aho.insert(str[i],i+1);
        }
        aho.getFail();
        scanf("%s",tot);
        aho.Find(tot);
        printf("%d\n",aho.all_su);
    }
    return 0;
}

尾节点记录可重复子串在总串中出现次数

#include<bits/stdc++.h>
using namespace std;

const int maxn=(int)500005;
const int max_tot=(int)1e6+6;

int T,N;
char str[10010][60],tot[max_tot];

struct AC_AutoMaton{
    static const int sigma_size=26;
    static const char first_caractar='a';
    int ch[maxn][sigma_size];
    int f[maxn],last[maxn];
    int cnt[maxn],val[maxn];
    int siz;

    int ans;

    void init(){
        siz=ans=0;
        memset(ch,0,sizeof(ch));
        memset(val,0,sizeof(val));
    }

    int ord(char c){
        return c-first_caractar;
    }

    void insert(char *s){
        int u=0,n=strlen(s);
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            if(!ch[u][c]) ch[u][c]=++siz;
            u=ch[u][c];
       }
       ///表示以第u棵节点为字符串最后一个字符节点的个数
       ///如果想存储该节点代表的是哪个字符串.即存储该字符串的下标
       ///val[u]=v;(v是下标)
       ///但是这样存储就会出现无法统计之前有多少个重复字符串
       ///比如这道题如果输入
       ///3
       ///sha
       ///sha
       ///sha
       ///shashasha
       ///则用第一种方法最后结果是3
       ///但用第二种方法只能匹配一次sha
       val[u]++;
    }
    //Fail树
    void getFail(){
        queue<int> Q;
        f[0]=0;
        ///遍历取出第一个节点所有的前向字符
        for(int c=0;c<sigma_size;++c){
            int u=ch[0][c];
            if(u){
                f[u]=last[u]=0;
                Q.push(u);
            }
        }
        while(!Q.empty()){
            int k=Q.front();
            Q.pop();
            for(int c=0;c<sigma_size;++c){
                int u=ch[k][c];
                if(!u) continue;
                Q.push(u);
                int v=f[k];
                while(v && !ch[v][c]) v=f[v];
                f[u]=ch[v][c];
                last[u]=val[f[u]]?f[u]:last[f[u]];
            }
        }
    }

    ///统计
    void add(int u){
        if(u){
            if(!cnt[u]) ans+=val[u],cnt[u]=1;
            add(last[u]);
        }
    }

    ///多模式匹配
    void Find(char *s){
        int u=0,n=strlen(s);
        memset(cnt,0,sizeof(cnt));
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            while(u && !ch[u][c]) u=f[u];
            u=ch[u][c];
            if(val[u]) add(u);
            else if(last[u]) add(last[u]);
        }
    }
}aho;

int main(){
    scanf("%d",&T);
    while(T--){
        aho.init();
        scanf("%d",&N);
        for(int i=0;i<N;++i){
            scanf("%s",str[i]);
            aho.insert(str[i]);
        }
        aho.getFail();
        scanf("%s",tot);
        aho.Find(tot);
        printf("%d\n",aho.ans);
    }
    return 0;
}

失配函数优化

接下来都基于第一个代码进行优化,可以复刻到第二个代码上

即将失配记录转变成 一条确定的边连到Trie中(这样应该就不能被称之为树了)

if(!u) continue; =>

if(!u) {ch[k][c]=ch[f[k]][c];continue;}
删掉适配函数BFS中的 while()

#include<bits/stdc++.h>
using namespace std;

const int maxn=(int)500005;
const int max_tot=(int)1e6+6;

int T,N;
char str[10010][60],tot[max_tot];

struct AC_AutoMaton{
    static const int sigma_size=26;
    static const char first_caractar='a';
    ///Trie树
    int ch[maxn][sigma_size];
    ///后缀相关数组
    int f[maxn],last[maxn];
    ///个数信息,尾节点记录信息
    int cnt[maxn],val[maxn];
    ///总节点个数
    int siz;

    int all_su;///记录总共有多少不可重复子串

    void init(){
        siz=all_su=0;
        memset(ch,0,sizeof(ch));
        memset(val,0,sizeof(val));
    }

    int ord(char c){
        return c-first_caractar;
    }

    void insert(char *s,int v){
        int u=0,n=strlen(s);
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            if(!ch[u][c]) ch[u][c]=++siz;
            u=ch[u][c];
       }
       ///尾节点记录字符串在str数组的下标
       val[u]=v;
    }

    //Fail树
    void getFail(){
        queue<int> Q;
        f[0]=0;
        ///遍历取出第一个节点所有的前向字符
        for(int c=0;c<sigma_size;++c){
            int u=ch[0][c];
            if(u){
                f[u]=last[u]=0;
                Q.push(u);
            }
        }
        while(!Q.empty()){
            int k=Q.front();
            Q.pop();
            for(int c=0;c<sigma_size;++c){
                int u=ch[k][c];
                if(!u) {ch[k][c]=ch[f[k]][c];continue;}
                Q.push(u);
                int v=f[k];
                f[u]=ch[v][c];
                last[u]=val[f[u]]?f[u]:last[f[u]];
            }
        }
    }

    ///统计
    void add(int u){
        for(;u;u=last[u]){
            if(!cnt[val[u]]) all_su++;
            printf("\n%s\n",str[val[u]-1]);
            cnt[val[u]]++;
        }
    }

    ///多模式匹配
    void Find(char *s){
        int u=0,n=strlen(s);
        memset(cnt,0,sizeof(cnt));
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            while(u && !ch[u][c]) u=f[u];
            u=ch[u][c];
            if(val[u]) add(u);
            else if(last[u]) add(last[u]);
        }
    }
}aho;

int main(){
    scanf("%d",&T);
    while(T--){
        aho.init();
        scanf("%d",&N);
        for(int i=0;i<N;++i){
            scanf("%s",str[i]);
            aho.insert(str[i],i+1);
        }
        aho.getFail();
        scanf("%s",tot);
        aho.Find(tot);
        printf("%d\n",aho.all_su);
    }
    return 0;
}

MLE和TLE优化–内存优化

听说之前网络赛的时候就有道AC自动机的题,然后普通的模板总是MLE.
少了一半的时间,一半的内存

意在每次不全初始化,每多一个节点初始化一次

#include<bits/stdc++.h>
using namespace std;

const int maxn=(int)500005;
const int max_tot=(int)1e6+6;

int T,N;
char str[60],tot[max_tot];

struct AC_AutoMaton{
    static const int sigma_size=26;
    static const char first_caractar='a';
    ///Trie树
    int ch[maxn][sigma_size];
    ///后缀相关数组fail,last
    int f[maxn];
    ///个数信息,尾节点记录信息
    int cnt[maxn],val[maxn];
    ///总节点个数,根节点编号
    int siz,root;

    int ans;

    int newNode(){
        memset(ch[siz],0,sizeof(ch[siz]));
        f[siz]=val[siz]=0;
        return siz++;
    }

    void init(){
        ans=0;siz=0;root=newNode();
    }

    int ord(char c){
        return c-first_caractar;
    }

    void insert(char *s){
        int u=root,n=strlen(s);
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            if(!ch[u][c]) ch[u][c]=newNode();
            u=ch[u][c];
       }
       val[u]++;
    }

    //Fail树,build
    void getFail(){
        queue<int> Q;
        Q.push(root);

        while(!Q.empty()){
            int k=Q.front();
            Q.pop();
            for(int c=0;c<sigma_size;++c){
                if(ch[k][c]){
                    f[ch[k][c]]=k?ch[f[k]][c]:0;
                    Q.push(ch[k][c]);
                }
                else ch[k][c]=ch[f[k]][c];
            }
        }
    }

    ///多模式匹配
    void Find(char *s){
        int u=0,n=strlen(s);
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            u=ch[u][c];
            int p=u;
            while(p && val[p]){
                ans+=val[p];
                val[p]=0;
                p=f[p];
            }
        }
    }
}aho;

int main(){
    scanf("%d",&T);
    while(T--){
        aho.init();
        scanf("%d",&N);
        for(int i=0;i<N;++i){
            scanf("%s",str);
            aho.insert(str);
        }
        aho.getFail();
        scanf("%s",tot);
        aho.Find(tot);
        printf("%d\n",aho.ans);
    }
    return 0;
}

但是以上自动机识别形如a,ab,abc,abcd这类子串会出问题,在刷题时发现的,下面重新用新的方法来解决这个问题,建议用下面的AC自动机

HDU 2222,上面的那些题,修改

#include<bits/stdc++.h>
using namespace std;

const int maxn=1000000+6;

int T,N,tot_len;
char str[maxn],len[maxn];

struct AC_AutoMaton{
    static const int sigma_size=26;

    int ch[maxn][sigma_size];

    int f[maxn];

    int cle[maxn],val[maxn];

    int siz,root,ans;

    int newNode(){
        for(int i=0;i<sigma_size;++i){
            ch[siz][i]=0;
        }
        f[siz]=val[siz]=0;
        return siz++;
    }

    void init(){
        for(int i=0;i<maxn;++i) val[i]=0;
        ans=0;
        siz=0;root=0;
        newNode();
    }

    int ord(char c){
        if(isupper(c))
            c=tolower(c);
        return (int)(c-'a');
    }

    void insert(char *s){
        int u=root,n=strlen(s);
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            if(!ch[u][c]) ch[u][c]=newNode();
            u=ch[u][c];
       }
       val[u]++;
    }

    void getFail(){
        queue<int> Q;
        Q.push(root);
        while(!Q.empty()){
            int k=Q.front();
            Q.pop();
            for(int c=0;c<sigma_size;++c){
                if(ch[k][c]){
                    f[ch[k][c]]=k?ch[f[k]][c]:0;
                    Q.push(ch[k][c]);
                }
                else ch[k][c]=ch[f[k]][c];
            }
        }
    }

    void add(int u,int i){
        while(u){
            if(val[u]){
                int t=len[val[u]];
                for(int r=0;r<t;++r){
                    cle[i-r]=1;
                }
                return;
            }
            u=f[u];
        }
    }

    void Find(char *s){
        int u=0,n=tot_len;
        for(int i=0;i<tot_len;++i) cle[i]=0;
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            ///下面这句加不加都一样
            //while(u && !ch[u][c]) u=f[u];
            u=ch[u][c];
            int p=u;
            while(p && val[p]){
                ans+=val[p];
                val[p]=0;
                p=f[p];
            }
        }
    }

}aho;

int main(){
    scanf("%d",&T);
    while(T--){
        aho.init();
        scanf("%d",&N);
        for(int i=0;i<N;++i){
            scanf("%s",str);
            aho.insert(str);
            len[i+1]=strlen(str);
        }
        getchar();
        aho.getFail();
        tot_len=0;
        gets(str);
        tot_len=strlen(str);
        aho.Find(str);
        printf("%d\n",aho.ans);
    }
    return 0;
}

HDU 5880,青岛区域赛网赛

#include<bits/stdc++.h>
using namespace std;

const int maxn=1000000+6;

int T,N,tot_len;
char str[maxn],len[maxn];

struct AC_AutoMaton{
    static const int sigma_size=26;

    int ch[maxn][sigma_size];

    int f[maxn];

    int cle[maxn],val[maxn];

    int siz,root;

    int newNode(){
        for(int i=0;i<sigma_size;++i){
            ch[siz][i]=0;
        }
        f[siz]=val[siz]=0;
        return siz++;
    }

    void init(){
        for(int i=0;i<maxn;++i) val[i]=0;

        siz=0;root=0;
        newNode();
    }

    int ord(char c){
        if(isupper(c))
            c=tolower(c);
        return (int)(c-'a');
    }

    void insert(char *s,int v){
        int u=root,n=strlen(s);
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            if(!ch[u][c]) ch[u][c]=newNode();
            u=ch[u][c];
       }
       val[u]=v;
    }

    void getFail(){
        queue<int> Q;
        Q.push(root);
        while(!Q.empty()){
            int k=Q.front();
            Q.pop();
            for(int c=0;c<sigma_size;++c){
                if(ch[k][c]){
                    f[ch[k][c]]=k?ch[f[k]][c]:0;
                    Q.push(ch[k][c]);
                }
                else ch[k][c]=ch[f[k]][c];
            }
        }
    }

    void add(int u,int i){
        while(u){
            if(val[u]){
                int t=len[val[u]];
                for(int r=0;r<t;++r){
                    cle[i-r]=1;
                }
                return;
            }
            u=f[u];
        }
    }

    void Find(char *s){
        int u=0,n=tot_len;
        for(int i=0;i<tot_len;++i) cle[i]=0;
        for(int i=0;i<n;++i){
            if(!isalpha(s[i])){
                u=0;
                continue;
            }
            int c=ord(s[i]);
            ///下面这句加不加都一样
            //while(u && !ch[u][c]) u=f[u];
            u=ch[u][c];
            /*
            int p=u;
            //cout<<i<<"  "<<u<<": "<<c<<endl;
            ///while是用来判断子串的.这道题不需要加
            while(p && val[p]){
                p=f[p];
            }
            */
            add(u,i);
        }
    }

    void print(){
        for(int i=0;i<tot_len;++i){
            if(cle[i]) putchar('*');
            else putchar(str[i]);
        }
        printf("\n");
    }
}aho;

int main(){
    scanf("%d",&T);
    while(T--){
        aho.init();
        scanf("%d",&N);
        for(int i=0;i<N;++i){
            scanf("%s",str);
            aho.insert(str,i+1);
            len[i+1]=strlen(str);
        }
        getchar();
        aho.getFail();
        tot_len=0;
        //scanf("%[^\n]",str);
        gets(str);
        tot_len=strlen(str);
        //cout<<tot_len<<endl;
        aho.Find(str);
        aho.print();
    }
    return 0;
}

后缀数组

后缀自动机