AC自动机学习笔记

作者: MayFlyyh 分类: 字符串 发布时间: 2018-12-22 10:15 ė 6 1条评论

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 的子树内。

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/500

一条评论

  1. Radiance 2019年1月2日 下午6:36 回复

    %%%

Radiance进行回复 取消回复

电子邮件地址不会被公开。

Captcha Code

Ɣ回顶部