AC自动机洛谷P3808 模板

题目链接:https://www.luogu.org/problem/P3808

题意：给n个模式串和一个文本串，求有多少个模式串在文本串中出现过

这个代码的时间复杂度为：O(N+M)但这是因为每个Trie上的点都只会经过一次，打了标记

如果不是只经过一次的话，这种没优化的代码的时间复杂度最坏为O(N*M);

有优化代码的时间复杂度分析：L个模式字符串（加总长度为N），以及长度为M大文本，用AC自动机可以在O(N+M)时间复杂度内解决这一问题，当L很大时，AC自动机的优势非常明显（kmp是O(L*M+N)）。

AC自动机的裸题，AC自动机最难理解的地方在于fail指针，这里借用了博客https://blog.csdn.net/creatorx/article/details/71100840#commentBox以及https://www.cnblogs.com/cjyyb/p/7196308.html的部分讲解

$f a i l$

举例：插入abcd, bce, abd, cd，构建字典树

首先我们让与根节点直接相连的节点的fail直接指向root,为了让你更好的理解fail指针，我们以节点x,y,z为例，我们让从图中我们可以看出x节点的fail指向了y节点，y节点的fail指向了z节点，为什么会这样指，因为x节点表示字符串abc,而字典树中含有最长，且以c结尾，且是abc的后缀的字符串bc(以y节点结尾的），同理，以y节点表示的字符串是bc,而以c结尾，且是bc的后缀的最长字符串是c（以z节点结尾的）。这就是fail指针指向的目标，那么我们得到了这个fail指针在匹配中有什么用呢，我们还是用上面的那个图来举例说明一下，假设文本串是abce,通过字典树我们可以看出，通过abc,所以我们可以匹配到x节点，但是到后面，我们发现d与e不匹配，这时我们就需要用到当前节点的fail了，因为x的fail指向的是y节点，所以我们直接跳到y节点，这是发现y节点后面有e，匹配上了，所以单词bce就在文本串abce中被检测出来了。当然这只是最简单的一种情况。

这里再解释一下代码中在求fail指针时为什么当前结点不存在就指向当前结点fail指针指向的结点的对应结点处，因为我们在查询有多少个子串的时候是加上所有达到的结点的数目（这个数目是指以这个节点结尾的单词的数目，且只加一次）。当我们遍历文本串时，遍历到了一个不存在的结点，用这种方法就可以直接转向前缀就是当前后缀的字符串了。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int inf=0x3f3f3f3f;
typedef long long ll;
#define meminf(a) memset(a,0x3f,sizeof(a))
#define mem0(a) memset(a,0,sizeof(a));
struct node{
    int fail;//失配指针fail
    int vis[26];//子节点的位置，也就是字典树的那26个字母
    int num;//记录有多少个单词以这个节点结尾 
}AC[maxn];
char s[maxn];
int cnt=0;//Trie的指针 

void insert(char *s){
    int len=strlen(s);
    int now=0;//字典树的当前指针
    for(int i=0;i<len;i++){
        //Trie树没有这个子节点 
        if(AC[now].vis[s[i]-'a']==0) AC[now].vis[s[i]-'a']=++cnt;
        now=AC[now].vis[s[i]-'a'];
    }
    AC[now].num++; 
}

void get_fail(){
    queue<int> que;
    for(int i=0;i<26;i++){//把第二层的fail指针都设为0 
        if(AC[0].vis[i]!=0)
        {
            AC[AC[0].vis[i]].fail=0;
            que.push(AC[0].vis[i]);
        }            
    }
    while(!que.empty())
    {
        int u=que.front();que.pop();
        for(int i=0;i<26;i++){
            if(AC[u].vis[i]!=0){
                //如果当前结点的子节点存在，就将子节点的fail指针指向当前结点fail指针指向的结点的对应子节点处 
                AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i];
                que.push(AC[u].vis[i]);
            }
            else AC[u].vis[i]=AC[AC[u].fail].vis[i];
            //否则直接将这个不存在的子节点指向当前结点fail指针指向结点的对应子节点处 
        }
    }
}

int AC_query(char* s){
    int len=strlen(s);
    int ans=0,now=0;
    for(int i=0;i<len;i++){
        now=AC[now].vis[s[i]-'a'];
        for(int t=now;t!=0&&AC[t].num!=-1;t=AC[t].fail){
            //能够抵达的结点都将该节点的单词数加上，但记得标记加过一次后就不要再加了
            //不加是因为因为这道题并不是统计所有子串出现的总数，而是有多少子串出现了 
            ans+=AC[t].num;
            AC[t].num=-1;
        }
    }
    return ans;
}
int main(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",s);
        insert(s);
    }
    AC[0].fail=0;//结束标志     
    get_fail(); //求出失配指针 
    scanf("%s",s);
    printf("%d
",AC_query(s)); 
    return 0;
}

AC自动机 洛谷P3808 模板

AC自动机洛谷P3808 模板