AC自动机学习笔记

用途

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

思想

要搞懂AC自动机，先得有模式树（Trie树）Trie和KMP模式匹配算法的基础知识。AC自动机算法分为3步：构造一棵Trie树，构造失败指针和模式匹配过程。

与KMP类似，AC自动机对于普通暴力的优化方式即是在与当前模式串失配后，找到其他模式串中与字符串公共前后缀最长的一个模式串，并且继续进行匹配。

譬如对于模式串①“ABCDG”，②”BCDE”，与文本串”ABCDE”，在与模式串①匹配到S[5]=“E”时，发生了失配，快速找到另一个模式串的前缀与匹配前（未匹配S[5]时）的后缀最长的一个模式串，也就是②（”BCD”），然后继续匹配。

复杂度 O(\sum n+m)

注：公共前后缀指串 s1 与串 s2，存在i_{s1},j_{s2}使s1的prefix(i_{s1})=subfix(j_{s2})

注：prefix(i) 指s[1….i]，subfix(i) 指 s[i….n]

注：rt 指 Trie 树的根节点，s[1….i] 指由字符 s[1],s[2],….s[i] 所构成的长度为i的字符串

构建

首先将所有模式串插入 Trie树 中。

其次构造 Fail 数组。

Fail 数组含义

​ Fail[x] 表示 与字符串 s[rt….x] （从 Trie 的根到节点 x 所组成的字符串）所具有最长公共前后缀的字符串是 字符串 s[rt….Fail[x]]。类似于KMP算法中的 next 数组

Fail数组构造方法

​ 通常使用BFS的方式构造，这样可以保证我们构造Fail[x]的顺序是由其在 Trie 树中深度从小到大的。（逐层扩展）

​ Fail[x]默认为空，指向 rt

​ ① 将 rt 的所有儿子加入队列

​ ② 寻找一个对于节点 x , 由 儿子 y , 不妨假设节点 x 所映射的字符为 ‘a’，节点 y 所映射的字符为 ‘b’

​ 如果在 Trie 树中，Fail[x]节点的儿子中存在与 y 相应的字符（在这里也就是’b’），

​ 那么 Fail[y] 便指向 Fail[x] 的这个儿子。

​ 否则令 x= Fail[x]，重复②操作。

​ 其中关于“最长”的证明是显然的。

void Fail_Build(){
    std::queue<int> q;
    q.push(rt);//rt=0
    memset(fail,0,sizeof(fail));
    while(!q.empty()){
        int now=q.front();q.pop();
        for(int i=0;i<26;++i){
            if(trie[now][i]){
                int k=now;
                while(k!=rt){
                    k=fail[k];
                    if(trie[k][i]){
                        fail[trie[now][i]]=trie[k][i];
                        break;
                    }
                }
                q.push(trie[now][i]);
            }
        }
    }
}

匹配

​ 对于匹配，类似于 Tire树 查找的过程，我们不断在 Trie 树上爬，对于未匹配的过程，我们从当前所处的节点 x 跳转到 Fail[x] 处，继续匹配。而如果当前节点 x 被打上了 Trie 树的 end 标记 （当前所处字符是某个匹配串的结尾），那么就说明文本串完整地匹配了这个匹配串。

inline int Find(char *s,int len){
    int now=rt,ans=0;
    for(int i=1;i<=len;++i){
        while(now&&!tire[now][s[i]-'a']) 
                now=fail[x];
        now=trie[now][s[i]-'a'];
        int k=now;
        while(k!=rt){
            if(end[k])
            ans++;// match sucessfully.
            k=fail[k];
        }
    }
    return ans;
}

优化与扩展

Trie 图

​ 我们发现，在构造 Fail 数组时，我们不断向前回溯直到找到所对应的 Fail 指针，该策略效率偏低。考虑使用Trie 图优化。Trie 图实际上是指在所有模式串全部插入 Trie 树后，Tire 树的形态已经固定后，对于节点 x ，如果不存在 Trie[x][y]，那么就令Trie[x][y]=Trie[Fail[x]][y]。对于构造 Fail 数组时 这是一个递归的过程，可能需要模拟便于理解为什么不破坏其仍为“最长”的性质。对于匹配时，每次可以直接将节点跳转到Trie[x][S[i]-‘a’]。

构造：

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];
        }

匹配：

void find(string s){
    int len=s.length();
    int k=rt;
    for(int i=0;i<len;++i){
        k=trie[k][s[i]-'a'];
        int t=k;
        while(t){
            ans++;
        }
    }
}

完整代码：

// Luogu P3796
#include<bits/stdc++.h>
using std::string;
using std::map;
map<int,string> mp; 
const int N = 1e5;
int n;
char s[N];
int trie[N][26];
int fail[N],end[N],rt,tot;
int tag[N];
void insert(string s){
    int len=s.length();
    int now=rt;
    for(int i=0;i<len;++i){
        if(!trie[now][s[i]-'a'])
            trie[now][s[i]-'a']=++tot;
        now=trie[now][s[i]-'a'];
    }
    end[tot]++;
    mp[tot]=s;
}
void build(){
    std::queue<int> q;
    for(int i=0;i<26;++i){
        if(trie[rt][i])
            q.push(trie[rt][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];
        }
    }
}
void find(string s){
    int len=s.length();
    int k=rt;
    for(int i=0;i<len;++i){
        k=trie[k][s[i]-'a'];
        int t=k;
        while(t){
            tag[t]+=end[t];
            t=fail[t];
        }
    }
}
int main(){
    while(scanf("%d",&n)&&n){
        memset(trie,0,sizeof(trie));
        memset(fail,0,sizeof(fail));
        memset(tag,0,sizeof(tag));
        memset(end,0,sizeof(end));
        rt=tot=0;
        for(int i=1;i<=n;++i){
            string s;
            std::cin>>s;
            insert(s);
        }
        build();
        string s;
        std::cin>>s;
        find(s);
        int wh=0;
        for(int i=1;i<=tot;++i)
            if(tag[i]>tag[wh]) wh=i;
        std::cout<<tag[wh]<<std::endl;
        for(int i=1;i<=tot;++i){
            if(tag[i]==tag[wh]){
                std::cout<<mp[i]<<std::endl;
            }
        }
        //std::cout<<tag[wh]<<std::endl<<mp[wh]<<std::endl;
    }
    return 0;
}

Fail 树

​ 我们将每个节点 x 与其指向的 Fail 数组的点 Fail[x] 连边（Fail[x] 为父亲）

add(Fail[x],x)

​ 则会发现所构造出的图是树形态的，我们称为 Fail 树

​ ①它的每个点都是一个字符串的前缀，而且每个字符串的每个前缀在这棵树上都对应着一个点。

​ ②每个点的父节点的字符串都是这个点字符串的后缀，并且树上没有更长的它的后缀。

​ 也就是说，所有以字符串S[1…i]的为结尾的字符串都在 i 的子树内。