学习笔记::AC自动机

最先开始以为和自动刷题机是一个东西。。。

其实就是kmp的一个拓展。学完kmp再学这个就会发现其实不难

1.kmp是一个串匹配一个串，但是当我们想用多个串匹配一个文本的时候，kmp就不行了，因此我们有了AC自动机

2.很明显我们用单词去匹配文本是肯定要一个一个枚举单词去匹配的，那么我们换个思路，用文本去匹配串。

3.AC自动机的原理：我不是很懂，口胡一下：

1.建立一颗trie，读入单词后把单词一个一个插入到trie

3.进行文本匹配。把文本放到AC自动机上。想象一下：把AC自动机的root看成一个入口，把串的开头放进去，串一个一个字符地跑进自动机里，每个字符都对应上了一个节点。（要不为什么叫自动机）

#include<bits/stdc++.h>
using namespace std;
#define N 1000010
struct trie
{
    int ch[26],fail,val,vis;
}t[N>>1];
int n,root,ans,cnt;
char s[N];
int q[N];
void ins(char s[])
{
    int now=root,len=strlen(s+1);
    for(int i=1;i<=len;i++)
    {
        int x=s[i]-'a';
        if(!t[now].ch[x]) t[now].ch[x]=++cnt;
        now=t[now].ch[x];
    }
    t[now].val++;
}
void construct_AC()
{
    int l=1,r=0;
    q[++r]=root;
    while(l<=r)
    {
        int u=q[l++];
        for(int i=0;i<26;i++)
        {
            int v=t[u].ch[i]; if(!v) continue;
            if(u==root) t[v].fail=root; 
            else 
            {
                int now=t[u].fail;
                while(now!=root&&!t[now].ch[i]) now=t[now].fail;
                if(t[now].ch[i]) now=t[now].ch[i];
                t[v].fail=now;
            }
            q[++r]=v;
        }
    }
}
void AC(char s[])
{
    int len=strlen(s+1),now=root;
    for(int i=1;i<=len;i++)
    {
        int u=s[i]-'a';
        while(now!=root&&!t[now].ch[u]) now=t[now].fail;
        if(t[now].ch[u])
        {
            now=t[now].ch[u];
            for(int pos=now;pos!=root&&!t[pos].vis;pos=t[pos].fail) 
            {
                ans+=t[pos].val; t[pos].vis=1;
            }
        }
    }
}
int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        memset(t,0,sizeof(t)); ans=0; cnt=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) 
        {
            scanf("%s",s+1);
            ins(s);
        }
        construct_AC();
        scanf("%s",s+1);
        AC(s);
        printf("%d
",ans);
    }
    return 0;
}