数据结构之AC自动机

AC自动机，学会了有助于AC~~

AC自动机相当于在Trie上跑KMP——用于解决字符串的多模板匹配问题。所谓的多模板匹配，是相对于单模板匹配而言。单模板匹配就是KMP中所说的给定一个模板串，在查询串里面寻找这个模板串（匹配），而多模板匹配顾名思义，也就是有多个模板串。对于这种问题，我们用KMP或者Trie当然是可以直接写的，只是复杂度过高罢了。

比如给定m个平均长度为a的模板串，一个长度为n的查询串。使用KMP做，只需要做m次匹配就好，复杂度O(m*(a+n))，使用Trie做，O(m*a)的建树，然后O(n)枚举a的后缀串b，然后在Trie里O(a)找到b的前缀，总复杂度O(a*(m+n))

AC自动机就不一样了，只需要O(m*a+n)的复杂度就行了~

就像前面所说的AC自动机就是在Trie上面跑KMP，首先Trie建树需要O(m*a)的时间，然后跑KMP查询则是O(n)，复杂度至此就分析完了，下面开始分析算法。

我们先来回忆一下KMP是怎么优化出来的——假如查询串A已经遍历到了i处，模板串B遍历到j处发生了失配，也就是说我们已经知道了A[0...i]的所有字符是啥，只需要将j转移到fail[j]使得B[0...fail[j]] == A[i-fail[j] ...i]，也就是找到A的后缀==B的前缀，然后对j指针进行转移。那么同样，AC自动机也是如此。当发生了失配的时候，需要进行跳转，它是怎么跳转的呢？只需要找到某一个模板串的前缀==A[0...i]的后缀即可——前缀自然是存在Trie里，后缀当然和当前匹配的模板串的后缀一样，也就是说也是存在于Trie里（因为模板串都在Trie里），那么只需要在Trie里同样也求出一个fail数组实现字符串之间的转移即可。

举个百度百科上面的例子，有模板串FG、HERS、HIS、SHE，建成Trie如下（这数字表示结点）：

虚线箭头就是fail的转移了，指向0(root)的就不解释了，其他的随便看两个，比如91与76之间有一个箭头，91表示SHE，76表示HERS的前缀HE，显然HE(76)是SHE(91)的前缀，所以有一个91指向76的箭头。再比如86和85之间有一个箭头，86表示字符串HERS，85表示SHE的前缀S，显然S(85)是HERS(86)的后缀，所以有一个86指向85的箭头。

现在对那些虚线箭头的意义有了一定了解，那么问题来了——再次看到91到76的箭头，假如再加一个模板串ERS，那么91的箭头是依旧指向76，还是转而指向ERS的E呢？

这个问题不难，91自然还是指向76了，毕竟E也是HE(76)的后缀啊，只需要从76指向ERS的E就好了啊~~

AC自动机很精巧，但理解起来并不难~~~

道理懂了，实现就看下面了（顺便一提，AC自动机不像KMP转移那么简单，它的转移可能会很复杂（毕竟是一棵Trie上面），所以AC自动机有一个优化，它有一个被称作后缀链接的last数组，就是fail的加强版，对于i会找到fail[i]，如果fail[i]不是模板结点，可能需要继续找下去，last便是存储这个最终结果的~）：

//用于求所有模板串在匹配串里共出现多少次，实现其他的需要稍微修改
//比如：如果要求有多少个模板串在匹配串里出现，则需要开一个vis[]防止重复访问
#define rgt register int

struct ACAutoMata
{
    int ch[maxnode][sigma_size];
    int val[maxnode];
    int f[maxnode];
    int last[maxnode];
    int sz;//结点总数
    ACAutoMata(){ sz = 1; memset(ch[0], 0, sizeof ch[0]);}
    void init()
    {
        sz = 1;
        memset(ch[0], 0, sizeof ch[0]);
        val[0] = 0;
    }
    int idx(char c) {   return c-'a';} // 字符c的编号

    // 插入字符串s，附加信息为v（例如字符串的权值等)，v非0，因为0表示本结点不是单词结点
    void insert(char* s, int v)
    {
        int u = 0, n = strlen(s);
        for(rgt i = 0; i < n; ++ i)
        {
            int c = idx(s[i]);
            if(!ch[u][c])//结点不存在
            {
                memset(ch[sz], 0, sizeof ch[sz]);
                val[sz] = 0;
                ch[u][c] = sz ++;
            }
            u = ch[u][c];//往下走
        }
        val[u] = v;//字符串的最后一个字符的附加信息为v
    }

    void print(int j)   //递归打印以结点j结尾的所有字符串
    {
        if(j)
        {
            printf("%d\n", val[j]);
            print(last[j]);
        }
    }

    int getFail()
    {
        queue<int> q;
        last[0] = f[0] = 0;
        for(rgt c = 0; c < sigma_size; ++ c)
        {
            int u = ch[0][c];
            if(u)   {   f[u] = 0; q.push(u); last[u] = 0;}
        }
        while(!q.empty())
        {
            int r = q.front(); q.pop();
            for(rgt c = 0; c < sigma_size; ++ c)
            {
                int u = ch[r][c];
                if(!u)  {   ch[r][c] = ch[f[r]][c]; continue;}
                q.push(u);
                int v = f[r];
                while(v && !ch[v][c])    v = f[v];
                f[u] = ch[v][c];
                last[u] = val[f[u]] ? f[u] : last[f[u]];
            }
        }
    }
    void find(char* T)
    {
        int n = strlen(T);
        int j = 0;
        for(rgt i = 0; i < n; ++ i)
        {
            int c = idx(T[i]);
            j = ch[j][c];
            if(val[j])          print(j);
            else if(last[j])    print(last[j]);
        }
    }
};