AC自动机

我们知道KMP可以在线性时间复杂度解决单模式匹配。但是对于多模式字符串匹配时，效率还是太低，那有没有只遍历一遍文本串的前提下，找到全部匹配模式串的算法呢。这就开始介绍多模式字符串匹配算法——AC自动机。

算法思想

AC自动机主要结合了 字典树（Trie） 和KMP中后缀函数（ne） 的思想——在这里是在trie树上跳跃，也就是我们俗称 fail指针 。如果当前点匹配失败，则将指针转移到fail指针指向的地方，这样就可以不用重头再来, 尽可能的利用已经知道的信息，能少退就少退 ,fail 指针的构建用 bfs 实现。

构建Trie树

构建实配指针Fail

使当前字符失配时跳转到具有最长公共前后缀的字符继续匹配。如同 KMP算法一样， AC自动机在匹配时如果当前字符匹配失败，那么利用fail指针进行跳转。跳转后的串的前缀，必为跳转前的模式串的后缀并且跳转的新位置的深度（匹配字符个数）一定小于跳之前的节点。所以我们可以利用 bfs在 Trie上面进行每一层节点 fail指针的求解。

匹配过程

以yasherhs为例，在Trie树开始都没有y和a节点，故从s（1）开始，依次匹配到he（2）（3），紧接着到r但是she后面已经没有字符了，故指向e的fail节点e（4），此时he确实是she的后缀，体现了fail指针的妙用，接下来发现e后面有r（5），此时已经成功匹配了she和he还有her三个字符。

接着到了h，同上面一样此时r后面已经没有了字符，指向它的fail指针root（6），找到其有h（7）儿子节点，但由于不是最终节点，故继续向后找s，同样当前儿子节点中没有s，指向其fail指针root（8），找到其有s（9）儿子节点，不是最终节点，且此时遍历结束，共找到3个匹配串she和he还有her。

代码

struct AC {
    int trie[N * 55][26]; //trie结构
    int fail[N * 55]; //fail失配指正
    int cnt[N * 55]; //节点末尾标记
    int q[N * 55]; //队列
    int idx;
    
    void init() { //初始化
        idx = 0;
        memset(trie, 0, sizeof trie);
        memset(fail, 0, sizeof fail);
        memset(cnt, 0, sizeof cnt);
    }
    
    void insert(char s[]) { //建立trie树
        int p = 0;
        for (int i = 0; s[i]; i ++) {
            int u = s[i] - 'a';
            if (!trie[p][u])
                trie[p][u] = ++ idx;
            p = trie[p][u];
        }
        cnt[p] ++;
    }
    
    void build() {  //构建AC自动机结构
        int hh = 0, tt = -1;
        for (int i = 0; i < 26; i ++) { //bfs字符头结点入队
            if (trie[0][i])
                q[++ tt] = trie[0][i];
        }
        
        while (hh <= tt) {
            int u = q[hh ++];
            for (int i = 0; i < 26; i ++) {
                int &v = trie[u][i]; // u:父节点,v:子节点
                if (v) {	// 如果子节点v存在，为点v填充失配指针fail
                    /*
                    利用并查集思想直接跳到fail指针最终跳到的位置
                    也就是跳到它父亲记录好的trie[fail[u]][i]位置上去
                    它的父亲对应值，是记录了祖先传递下来的，不用再回溯求递归求解
                    */
                    fail[v] = trie[fail[u]][i]; 
                    q[++ tt] = v; // 入队列
                } else {
                    v = trie[fail[u]][i]; // 如果不存在，也要纪录其值，后面遍历需要它来提供信息。
                }
            }
        }
        
        
    }
    
    int query(char s[]) {
        int ans = 0;
        int j = 0;
        for (int i = 0; s[i]; i ++) {	// 枚举文本串每个字符
            int u = s[i] - 'a';
            // 如果没有回退到根，并且，当前没有u这条边，继续利用失配指针回退
            while(j && trie[j][u] == 0)
                j = fail[j];
            // 找到匹配的失配节点
            if (trie[j][u])
                j = trie[j][u];
            
            // 统计在当前失配节点向根游走，有多少个完整的模式串被命中
            int p = j;
            while(p && ~cnt[p]) {
                ans += cnt[p]; // 统计个数
                cnt[p] = -1;   // 标记，重复字符只统计1次
                p = fail[p];	// 不断回退
            }
        }
        return ans;
    }
}ac;

Q.E.D.