简介

AC自动机，就算没学也肯定听过这个名字，并且让人觉得可以用这个算法自动A题(

学起来其实也不是很难，自己画个图啥都理解了233

大佬们都总结AC自动机是trie+kmp

实际上也的确挺形象的

AC自动机的作用是用来匹配多个字符串的

就是给出一堆单词问一个句子中出现了多少个不同单词什么的题目

前置技能

kmp

trie

核心内容

插入

插入字符串和trie完全一样，没什么讲的

il void ins(char *s)
{
    int u=0;
    for(int i=0;s[i];i++)
    {
        int v=s[i]-'0';
        if(!e[u][v]) e[u][v]=++cnt;
        u=e[u][v];
    }
    v[u]=1;
}

构造fail指针

fail指针的作用是什么呢？当然是匹配失败后跳到的位置

那么是如何匹配的呢？

首先在一个句子中

用一个指针从前往后扫

一开始从根出发，一直按指针当前的字母往下走，

当失配的时候

跳到失配的位置

这个位置使原来后缀和现在前缀有最长公共序列

嘛，怎么理解呢

比如

lyzqsqwqwq
lyzqsqaq
     qwqwq

fail指针的作用就算让上图w和a失配时，使a跳到满足前缀和当前单词后缀有最长公共序列的位置上

然后就可以匹配下一个单词了

那么如何构造呢

类似kmp，用到之前节点信息

一遍bfs就可以了

具体多看看代码就懂了233

queue<int> q;
il void build()
{
    for(int i=0;i<26;i++) if(e[0][i]) fl[e[0][i]]=0,q.push(e[0][i]);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=0;i<26;i++)
        {
            if(e[u][i])
            {
                fl[e[u][i]]=e[fl[u]][i];
                q.push(e[u][i]);
            }
            else e[u][i]=e[fl[u]][i];//这里可以加速，方便跳转
        }
    }
}

询问

上面讲的很清楚了，对于一个字符串，拿一个指针扫，然后一直跳就完事了233

il int qry(char *s)
{
    int l=strlen(s);
    int res=0,u=0;
    for(int i=0;i<l;i++)
    {
        u=e[u][s[i]-'a'];
        for(int j=u;j&&~v[j];j=fl[j]) 
            res+=v[j],v[j]=-1;//根据统计方法修改代码，这里每个单词只统计一次
    }
    return res;
}

总结

AC自动机其实多画画图就很容易理解了233

⑧说了，SASAM真难学，我去学习了