欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

简单版AC自动机

程序员文章站 2022-12-14 21:15:34
简单版$AC$自动机 学之前听别人说起一直以为很难,今天学了简单版的$AC$自动机,感觉海星,只要理解了$KMP$一切都好说。 前置知识: "$KMP$" (有链接) 前置知识:$Trie$树 字典树($Trie$树)比较简单,就是把许多个单词通过树连接起来。每个点记录一下儿子个数以及是否是单词结尾 ......

简单版\(ac\)自动机

学之前听别人说起一直以为很难,今天学了简单版的\(ac\)自动机,感觉海星,只要理解了\(kmp\)一切都好说。

前置知识:\(kmp\)(有链接)

前置知识:\(trie\)

字典树(\(trie\)树)比较简单,就是把许多个单词通过树连接起来。每个点记录一下儿子个数以及是否是单词结尾即可。每次加入一个单词时,从第一个字母开始搜索,如果当前字母存在,就从该字母的儿子里找下一个字母,否则就新建一个节点,直到把这个单词全部加入进去,然后在最后的字符上标记一下表示以这个字母结尾的单词多了一个。

那么\(ac\)自动机实际上就是将两者合并了起来,在字典树上进行\(kmp\)

先说一下\(ac\)自动机是干什么的。一个常见的例子就是给出n个单词,再给出一段包含m个字符的文章,让你找出有多少个单词在文章里出现过。要搞懂ac自动机,先得有模式树(字典树)\(trie\)\(kmp\)模式匹配算法的基础知识。\(kmp\)算法是单模式串的字符匹配算法,\(ac\)自动机是多模式串的字符匹配算法。

说白了就是给你一堆字符串,然后再给你一个字符串,问最后这个字符串中出现了多少个前面给出的字符串。

首先我们要有一个字典树。对于给出的那一堆字符串,我们要一个一个加到树里。代码如下:

struct ac{//字典树
    int end,vis[26],fail;//vis表示儿子的编号
}ac[1000006];
int cnt;
void build(string s){//要加入的单词
    int l=s.length(),now=0;//now是当前节点
    for(int i=0;i<l;++i){
        if(ac[now].vis[s[i]-'a']==0) ac[now].vis[s[i]-'a']=++cnt;
        //如果这个字母没有,就新建一个
        now=ac[now].vis[s[i]-'a'];//如果有或者已经建好,就往下跳
    }
    ac[now].end++;//在最后一个字母处标记有几个单词以它结尾
}

有了字典树,考虑怎样在树上进行\(kmp\)

\(kmp\)里面的\(next\)指针在这里改成\(fail\),其实都一样。

每个节点\(t\)\(fail\)指针,其所指向的节点和\(t\)节点的字符是一样的。因为如果\(t\)匹配成功,而\(t\)的儿子匹配失败,那么需要从\(t\)\(fail\)指针的儿子节点开始匹配。

\(fail\)指针用\(bfs\)来求。

首先,根节点的\(fail\)指针显然指向他自己,即\(0\)。而他的儿子,也就是深度为一的节点的指针也是指向他的。那么考虑剩下的节点\(t\)。它的父亲节点的\(fail\)指针已经知道,那么这个指针指向的节点假如是\(u\)的话,如果\(u\)有一个和\(t\)一样的节点,那么\(t\)\(fail\)指针就应该指向它,如果没有,就要从\(father->fail->fail\)里找,直到找到相同的节点或者到根节点。也就是说要顺着之前的失配指针走一遍,有点麻烦。

考虑如果当前节点没有某个字母,那么我们可以将该节点指向这个字母的指针,指到他的失配指针指向的节点的这个字母上。

if(ac[u].vis[i]==0)
    ac[u].vis[i]=ac[ac[u].fail].vis[i];

这样就不用沿着失配指针走一遍了。代码如下:

void get_fail(){
    queue<int>q;//队列,bfs
    for(int i=0;i<26;++i)//处理深度为二的点
        if(ac[0].vis[i]) ac[ac[0].vis[i]].fail=0,q.push(ac[0].vis[i]);
    while(!q.empty()){
        int u=q.front();
        for(int i=0;i<26;++i)
            if(ac[u].vis[i]) ac[ac[u].vis[i]].fail=ac[ac[u].fail].vis[i],q.push(ac[u].vis[i]);
            //如果有这个点,就直接更新指针并压入队列
            else ac[u].vis[i]=ac[ac[u].fail].vis[i];//没有就按上述方法处理
        q.pop();
    }
}

最后就是统计了。

对于每个字母,如果他是几个单词的结尾,那么久加上他的以及他的所有失配指针的答案,因为他可以,他的失配指针同样可以。

代码:

int ac_query(string s){
    int l=s.length(),now=0,ans=0;
    for(int i=0;i<l;++i){
        now=ac[now].vis[s[i]-'a'];
        for(int t=now;t&&ac[t].end!=-1;t=ac[t].fail)//沿着失配指针跳
            ans+=ac[t].end,ac[t].end=-1;//统计答案,标记-1为了防止重复统计
    }
    return ans;
}

\(code\)

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
struct ac{
    int end,vis[26],fail;
}ac[1000006];
int cnt;
void build(string s){
    int l=s.length(),now=0;
    for(int i=0;i<l;++i){
        if(ac[now].vis[s[i]-'a']==0) ac[now].vis[s[i]-'a']=++cnt;
        now=ac[now].vis[s[i]-'a'];
    }
    ac[now].end++;
}
void get_fail(){
    queue<int>q;
    for(int i=0;i<26;++i)
        if(ac[0].vis[i]) ac[ac[0].vis[i]].fail=0,q.push(ac[0].vis[i]);
    while(!q.empty()){
        int u=q.front();
        for(int i=0;i<26;++i)
            if(ac[u].vis[i]) ac[ac[u].vis[i]].fail=ac[ac[u].fail].vis[i],q.push(ac[u].vis[i]);
            else ac[u].vis[i]=ac[ac[u].fail].vis[i];
        q.pop();
    }
}
int ac_query(string s){
    int l=s.length(),now=0,ans=0;
    for(int i=0;i<l;++i){
        now=ac[now].vis[s[i]-'a'];
        for(int t=now;t&&ac[t].end!=-1;t=ac[t].fail)
            ans+=ac[t].end,ac[t].end=-1;
    }
    return ans;
}
int main(){
    int n;
    string s;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>s,build(s);
    ac[0].fail=0;
    get_fail();
    cin>>s;
    cout<<ac_query(s);
    return 0;
}