AC 自动机

介绍

Aho-Corasick automaton，是著名的多模匹配算法。

一个常见的例子就是给出 n 个单词，再给出一段包含 m 个字符的文章，让你找出有多少个单词在文章里出现过。

详解

AC 自动机就是 Trie 树上的 KMP。

详见代码：Code

AC 自动机的关键点与 KMP 一样，需要构建出失配指针 fail[] 数组（也就是 KMP 的 next[] ）。

fail[] 构建的核心代码（即下面程序中的 nxt[] ）

void bfs()
{
    for(int i=0;i<=25;++i)
        ch[0][i]=1;//0 结点的每一个字符都指向 root 结点（初始化） 
    que[1]=1;
    nxt[1]=0;//构建 nxt 数组，root 默认指向 0 结点 
    for(int q1=1,q2=1;q1<=q2;++q1)//BFS 
    {
        int u=que[q1];
        for(int i=0;i<=25;++i)
        {
            if(!ch[u][i])//如果到叶子结点的话则通过 nxt 往回跳 
                ch[u][i]=ch[nxt[u]][i];
            else
            {
                que[++q2]=ch[u][i];
                int v=nxt[u];
                //符合条件的 v ：查找父亲的前缀指针(nxt)指向的节点，通过 nxt 一直跳， 
                //直到找到该结点的有通过 i 连接的儿子 
                while(v>0 && !ch[v][i])//通过 nxt 一直跳直到找到符合的 
                    v=nxt[v];
                nxt[ch[u][i]]=ch[v][i];//nxt 的跳转 
            }
        }
    }
}

---

注：部分资料来源于百度百科

---

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.