假设手里有N个串，和原文进行匹配，如果跑KMP，得把原文跑N次，实在是太费时间了。AC自动机借助于Trie的压缩功能，将多个串压成一个“树”，用这个树进行KMP，这就是贝尔实验室发明的AC自动机。

AC自动机主要有三个操作；insert，getfail，print，find。

insert的操作和Trie一样。

void Insert(string str,int v){    int u=0,c;    for(int i=0;i

getfail采用BFS，逐个检查，记录后缀链接last数组

void GetFail(){    queue
       
         Q;    f[0]=0;    for(int c=0;c<26;c++)    {        int u=ch[0][c];        if(u)        {            f[u]=last[u]=0;            Q.push(u);        }    }    while(!Q.empty())    {        int r=Q.front();Q.pop();        for(int c=0;c<26;c++)        {            int u=ch[r][c];            if(!u)            {                ch[r][c]=ch[f[r]][c];                continue;            }            Q.push(u);            int v=f[r];            while(v&&!ch[v][c]) v=f[v];            f[u]=ch[v][c];            last[u]=val[f[u]]?f[u]:last[f[u]];        }    }}
       

find对应的是原文

void Find(string str){    int j=0,c;    for(int i=0;i

print表示在确定一个串后的操作

void print(int j){    if(j)    {        cnt[val[j]]++;        print(last[j]);    }}

整个自动机中，最重要的是后缀链接last数组的使用，对于一个单词的尾结点，可能对应多个串，需要沿着往回走，看看有没有串了。

 

@练习题

HDU 2222

HDU 2896

HDU 3065