引入

我们发现\(Trie\)树可以进行多模式串匹配，\(KMP\)可以快速进行子串匹配，那么如果我们要进行多模式串子串匹配怎么办呢？这里我们就将介绍一个综合了\(Trie\)树和\(KMP\)的算法——\(AC\)自动机。

简述

上面已经提到了\(AC\)自动机就是\(Trie\)树和\(KMP\)的综合，如果还不会或者不熟悉这两种算法的话请移步。

我们首先要建出一棵\(Trie\)树来，和普通的\(Trie\)树一样的。

代码如下：

void insert(char *s){    int p=0,len=strlen(s);    for(int i=0;i

然后我们就需要和\(KMP\)一样构建失配指针，也就是\(fail\)指针。而与\(KMP\)算法不同的是\(KMP\)算法的\(fail\)指针是相同的前后缀，而\(AC\)自动机只需要相同后缀就可以了。

那么我们应该如何构建呢？我们同样也是利用已经求得的\(fail\)指针来推导出当前节点的\(fail\)指针。我们采用\(BFS\)的方式来实现这个过程。我们设现在的节点为\(x\)，它的父亲节点为\(fa_x\)，它和它的父亲之间通过字符为\(ch\)的边连接，且深度小于\(x\)的所有节点的\(fail\)指针都已经求得。

• 我们首先跳转到\(fail[fa_x]\)节点
  • 如果\(fail[fa_x]\)节点有一个子节点\(y\)是由该节点通过字符为\(ch​\)的边连接的
    • 让\(x\)的\(fail\)指针指向\(y\)，即\(fail[x]=y\)
  • 如果不存在这样的节点
    • 那么就跳转到\(fail[fa_x]\)的\(fail\)指针指向的节点，即\(fail[fail[fa_x]]\)，然后重复上述过程
    • 如果一直跳转到根节点依然没有满足条件的节点的话，就让\(x\)的\(fail\)指针指向根节点，即\(fail[x]=root\)

上述过程便是\(fail\)指针的构建过程了。

对于字符串集合\(\{hers,his,she,i\}\)构建出来的\(fail\)指针如下：

代码如下：

void make_fail(){    queue
    
     q;    memset(fail,0,sizeof(fail));    for(int i=0;i<26;i++)if(trie[0][i])q.push(trie[0][i]);    while(!q.empty()){        int x=q.front();q.pop();        for(int i=0;i<26;i++){            if(trie[x][i]){                fail[trie[x][i]]=trie[fail[x]][i];                q.push(trie[x][i]);            }else trie[x][i]=trie[fail[x]][i];        }    }}
    

我们注意到上面的构建\(fail\)指针的代码中trie[x][i]=trie[fail[x]][i]这句话，为什么直接将\(fail[x]\)的子节点直接赋给\(x\)了呢？其实这行代码和上面两行的fail[trie[x][i]]=trie[fail[x]][i]共同做了类似于并查集的“路径压缩”的事情，也就是使得本身可能要跳转很多次的\(fail\)指针变成只需要跳转一次，这个可以感性理解一下。

匹配函数的代码如下：

int query(char *s){    int p=0,ret=0,len=strlen(s);    for(int i=0;i

\(p\)就是当前在\(Trie\)树上的节点，然后利用\(fail\)指针来找出所有匹配的模式串。但是我们发现一个问题，p=trie[p][ch]这行代码告诉我们\(p\)似乎是不断向后跳的，并没有像\(KMP\)一样跳到失配指针指向的节点。但其实并不然，我们看一下之前的构造\(fail\)指针的代码，我们发现，我们其实是对\(Trie\)树进行了改造的。所以，我们并不是不断向后跳的，我们同样的实现了跳\(fail\)指针的操作。

以上便是\(AC\)自动机的构造失配指针和匹配过程。

总代码如下：

struct AC_automaton{    int tot,ed[maxn],fail[maxn],trie[maxn][26];    void insert(char *s){        int p=0,len=strlen(s);        for(int i=0;i