AC自动机(Aho-Corasick automaton)

AC自动机(Aho-Corasick automaton)

第一次听说AC自动机,以为是accept自动机,然后才知道是Aho-Corasick发明的一种自动机,简称AC自动机。不过我有个同学,曾经写过accept自动机(滑稽.jpg),并且成功AC。

引用百度百科的一句话:

Aho-Corasick automaton,该算法在1975年产生于贝尔实验室,是著名的多模匹配算法。

要学会AC自动机,我们必须知道什么是Trie,也就是字典树。Trie树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。

字典树 KMP

AC自动机,就是在Trie树上做KMP,可以快速匹配多个字符串。

例题洛谷P3808 LOJ10057

AC自动机还可以用来做DP,这个就要多刷题了。

接下来引用一位dalao的课件,过程将的很清楚。

是不是立刻就懂了呢?

AC自动机的复杂度是O(平均长度*(串个数+文章长度))

那么我们来看代码吧!

//LOJ10057 
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXM=1000005,MAXN=10005,MAXI=30,MAXL=55;
char ss[MAXM];int n;
struct AhoC{
    int que[MAXN*MAXL],Son[MAXN*MAXL][MAXI],pre[MAXN*MAXL],Root,cnt,W[MAXN*MAXL];
    //que用于BFS,Son表示字典树上子节点的位置,pre表示失配节点的位置,Root是根,cnt当前的节点数,W[x]在x节点结束的单词个数 
    void clear(){memset(Son,0,sizeof(Son));memset(pre,0,sizeof(pre));memset(W,0,sizeof(W));cnt=Root=0;}
    int get(char ch){return ch-'a';}
    void Insert(char *s){//建出一棵字典树 
        int Now=Root;
        for(int i=0,Len=strlen(s),x;i<Len;i++){
            if(!Son[Now][x=get(s[i])]) Son[Now][x]=++cnt;
            Now=Son[Now][x];
        }
        W[Now]++;
    }
    void Build(){//找到失配节点 
        int hd=0,tl=0;
        for(int i=0;i<26;i++)//根是虚拟节点,向根节点连边,可以认为是初始化 
        if(Son[Root][i]) pre[que[++tl]=Son[Root][i]]=Root;
        else Son[Root][i]=Root;

        while(hd!=tl){//BFS
            int x=que[++hd];
            for(int i=0;i<26;i++){
                int y=Son[x][i];//找y的失配节点 
                if(y){
                    int f=pre[x];//y的失配节点是x的失配节点的儿子节点,当然当前位要相同 
                    while(f&&!Son[f][i]) f=pre[f];//如果没有对应的儿子,那么继续往失配节点走 
                    pre[y]=Son[f][i],que[++tl]=y; 
                }else Son[x][i]=Son[pre[x]][i];//如果x没有i这个儿子,那么就连一条虚边向失配节点的儿子 
            }
        }
    }
    int Query(char *s){
        int Len=strlen(s),x=Root,Ans=0;
        for(int i=0;i<Len;i++){
            int w=get(s[i]);
            while(x&&!Son[x][w]) x=pre[x];//如果不匹配,往失配节点跳 
            if(Son[x][w]){//匹配 
                int p=(x=Son[x][w]);//继续走 
                while(p&&W[p]!=-1) Ans+=W[p],W[p]=-1,p=pre[p];//计算答案,-1表示计算过了,如果计算过了,那么就可以跳过了。 
            }
        }
        return Ans;
    }
}Tre;
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    int T;
    for(scanf("%d",&T);T;T--){
        scanf("%d",&n);Tre.clear();
        for(int i=1;i<=n;i++){
            char s[55];scanf("%s",s);
            Tre.Insert(s);
        }
        Tre.Build(),scanf("%s",ss);
        printf("%d\n",Tre.Query(ss));
    }
    return 0;
} 

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部