AC自动机

AC自动机等于trie+kmp

扩展:trie图

KMP

暴力做法

s为长串 p为小串
for(int i=1;i<=s.size();i++)
 for(int j=1;j<=p.size();j++)
       if(s[i+j-1]!=p[j])
            break;
if(j>m)
    匹配成功

next数组定义就是下一次最近的能成功的位置 在p串中以p[i]结尾的后缀 能够匹配的从1开始的非平凡前缀的最大长度(这里的p串是短串)

步骤:

1.next[0]=next[1]=0;

2.

   //求next的过程
   for(int i=2,j=0;i<=n;i++)
   {
       while(j&&p[i]!=p[j+1]) j=ne[j];
       if(p[i]==p[j+1]) j++;
       ne[i]=j;
   }

//kmp
#include
using namespace std;
const int N=1e5+10,M=1e6+10;
int n,m,ne[N];
char p[N],s[M];
int main()
{
    ios_base::sync_with_stdio(0);//加速器
    cin.tie(0);
    cout.tie(0);
   cin>>n>>p+1>>m>>s+1;//读入数据
   //求next的过程
   for(int i=2,j=0;i<=n;i++)
   {
       while(j&&p[i]!=p[j+1]) j=ne[j];
       if(p[i]==p[j+1]) j++;
       ne[i]=j;
   }
   //kmp匹配过程
    for(int i=1,j=0;i<=m;i++)
   {
       while(j&&s[i]!=p[j+1]) j=ne[j];
       if(s[i]==p[j+1]) j++;
       if(j==n)//匹配成功
        {
        cout<' ';//输出答案
         j=ne[j];
       }
   }
    return 0;
}

---

AC自动机存的next是以这个点为结尾的所有后缀里面和某个最长前缀匹配 存的是最长前缀的结尾下标

 kmp对应到AC自动机

1.搜索关键词

信息学奥赛一本通（C++版）在线评测系统 

#include
using namespace std;
const int N=10010,S=55,M=1000010;
int n;
int tr[N*S][26],cnt[N*S],idx;
char str[M];
int q[N*S],ne[N*S];
void insert()//tire树
{
    int p=0;//从头结点开始插
    for(int i=0;str[i];i++)
    {
        int t=str[i]-'a';//映射到数字
        if(!tr[p][t]) tr[p][t]=++idx;//假如这个位置没有这个字母，则新开辟个节点
        p=tr[p][t];//跳到这个位置
    }
    cnt[p]++;//这个位置的单词++
}
void build()//求next数组的过程
{
    int hh=0,tt=-1;
    for(int i=0;i<26;i++)//把第一层的先入队
        if(tr[0][i])
           q[++tt]=tr[0][i];
    while(hh<=tt)
    {
        int t=q[hh++];//取出队头
        for(int i=0;i<26;i++)//枚举子节点
        {
            int c=tr[t][i];
            if(!c) continue;//假如这个位置没有这个节点，则直接跳
            int j=ne[t];
            while(j&&!tr[j][i]) j=ne[j];//假如匹配不成功则继续跳
            if(tr[j][i]) j=tr[j][i];//成功就为这个位置
            ne[c]=j;//这个节点的next更新一下
            q[++tt]=c;//把这个节点入队
        }
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        //清空上一层的状态
        memset(tr,0,sizeof tr);
        memset(cnt,0,sizeof cnt);
        memset(ne,0,sizeof ne);
        idx=0;
        scanf("%d",&n);
        for(int i=0;i
        {
            scanf("%s",str);
            insert();//插入这个单词
        }
        build();//求next数组
        scanf("%s",str);
        int res=0;
        for(int i=0,j=0;str[i];i++)//next匹配的过程
        {
            int t=str[i]-'a';
            while(j&&!tr[j][t]) j=ne[j];//假如这个位置匹配不上，则继续跳
            if(tr[j][t]) j=tr[j][t];//假如匹配了，则等于这个位置
            int p=j;
            while(p)//枚举p所重复的单词
            {
                res+=cnt[p];
                cnt[p]=0;//把这个位置的单词清空
                p=ne[p];//继续枚举上一个单词
            }
        }
        printf("%d\n",res);
    }
    return 0;
}

AC自动机优化成trie图 可以优化常数

优化的位置是求next数组的位置跟next匹配的过程

void build()//求next数组的过程
{
    int hh=0,tt=-1;
    for(int i=0;i<26;i++)//把第一层的先入队
        if(tr[0][i])
           q[++tt]=tr[0][i];
    while(hh<=tt)
    {
        int t=q[hh++];//取出队头
        for(int i=0;i<26;i++)//枚举子节点
        {
            int p=tr[t][i];
            if(!p) tr[t][i]=tr[ne[t]][i];//假如这个节点不存在，直接就跳到上一层的节点
            else
            {
                ne[p]=tr[ne[t]][i];//让这个节点等于上一层的节点
                q[++tt]=p;//放进队列里
            }
        }
    }
}
for(int i=0,j=0;str[i];i++)//next匹配的过程
{
            int t=str[i]-'a';
            j=tr[j][t];//因为优化的是直接等于next跳完后的值,所以直接跳到这个位置
            int p=j;
            while(p)//枚举p所重复的单词
            {
                res+=cnt[p];
                cnt[p]=0;//把这个位置的单词清空
                p=ne[p];//继续枚举上一个单词
            }
}

2.修复DNA（状态机+AC自动机）

3691 -- DNA repair

题意相当于给定我们一系列字符串，然后最后给我们一个长的字符串，问我们至少改变这个字符串的多少个字母使得这个长的字符串不包含前面输入的一系列字符串

 

#include
#include
#define min(a,b) a>b?b:a
const int N=1010;
int n,m;
int tr[N][4],dar[N],idx;//tr就是tire，dar就是标记这个单词是否存在
char str[N];
int q[N],ne[N];
int f[N][N];//f就是状态机dp的f函数
int get(char c)//把字母映射到数字里
{
    if(c=='A') return 0;
    if(c=='T') return 1;
    if(c=='G') return 2;
    return 3;
}
void insert()//tire的插入
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int t=get(str[i]);
        if(!tr[p][t]) tr[p][t]=++idx;
        p=tr[p][t];
    }
    dar[p]=1;//标记这个结尾的单词是存在的
}
void build()//求next数组
{
    int hh=0,tt=-1;
    for(int i=0;i<4;i++)//把第一层放进队列中
        if(tr[0][i])
          q[++tt]=tr[0][i];
    while(hh<=tt)
    {
        int t=q[hh++];//求出队头
        for(int i=0;i<4;i++)//枚举下一层的节点
        {
            int p=tr[t][i];
            if(!p) tr[t][i]=tr[ne[t]][i];//假如这个节点不存在，则直接跳到存在的节点上
            else
            {
                ne[p]=tr[ne[t]][i];//存在则直接跳即可
                q[++tt]=p;
                dar[p]|=dar[ne[p]];//把这个单词标记为危险DNA序列
            }
        }
    }
}
int main()
{
    int T=1;
    while(scanf("%d",&n),n)
    {
        //清空上一层的状态
        memset(tr,0,sizeof tr);
        memset(dar,0,sizeof dar);
        memset(ne,0,sizeof ne);
        idx=0;
        for(int i=0;i
        {
            scanf("%s",str);
            insert();//插入这个单词
        }
        build();//求next数组
        scanf("%s",str+1);
        m=strlen(str+1);
        memset(f,0x3f,sizeof f);//因为要求最小值，则初始化为正无穷
        f[0][0]=0;//从0个开始匹配到AC自动机第0个字母最小修改0次
        for(int i=0;i//枚举串的长度
            for(int j=0;j<=idx;j++)//枚举所有危险的单词
               for(int k=0;k<4;k++)//枚举危险单词的字母
               {
                 int t=get(str[i+1])!=k;//看看这个单词是否等于第k个位置
                 int p=tr[j][k];//获取危险单词的这个位置的字母
                 if(!dar[p]) f[i+1][p]=min(f[i+1][p],f[i][j]+t);//假如不存在这个危险单词，则更新最小值
               }
        int res=0x3f3f3f3f;
        for(int i=0;i<=idx;i++) res=min(res,f[m][i]);//枚举所有需要更新的最小
        if(res==0x3f3f3f3f) res=-1;
        printf("Case %d: %d\n",T++,res);
    }
    return 0;
}

3.单词

信息学奥赛一本通（C++版）在线评测系统

相当于问其他子串里有多少个后缀与原串匹配。则反向递推求这个后缀匹配多少个前缀，相当于让f[i]出现的次数累加到f[next[i]]里面，按照拓扑序递推回去next[i]然后累加就行了

#include
using namespace std;
const int N=1000010;
int n;
int tr[N][26],f[N],idx;//f记录的是以这个结尾的单词的数量
int q[N],ne[N];
char str[N];
int id[210];
void insert(int x)//tire的插入
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int t=str[i]-'a';
        if(!tr[p][t]) tr[p][t]=++idx;
        p=tr[p][t];
        f[p]++;//因为记录的是前缀，则在内部就记录这个值了
    }
    id[x]=p;//
}
void build()
{
    int hh=0,tt=-1;
    for(int i=0;i<26;i++)//把第一层的节点放进队列中
        if(tr[0][i])
         q[++tt]=tr[0][i];
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=0;i<26;i++)//枚举可能的子节点
        {
            int p=tr[t][i];
            if(!p) tr[t][i]=tr[ne[t]][i];//假如不存在这个节点，则直接跳他的上一个节点
            else
            {
                ne[p]=tr[ne[t]][i];//直接跳上一层的节点
                q[++tt]=p;//放进队列里
            }
        }
    }
}
int main()
{
   scanf("%d",&n);
   for(int i=0;i
   {
       scanf("%s",str);
       insert(i);//插入这个字符串
   }
   build();//求next数组
   for(int i=idx-1;i>=0;i--) f[ne[q[i]]]+=f[q[i]];//因为bfs搜索更新后的逆序就是拓扑序
   for(int i=0;iprintf("%d\n",f[id[i]]);
    return 0;
}