AC自动机（Aho-Corasick automaton）是一种多模式匹配算法。
字典树的典型应用是给定n个单词和一个包含m个单词的文章，统计总共有多少单词出现在文章中。
正常利用KMP算法，该问题的复杂度也达到了O（m^2），但AC自动机利用fail指针避免了多模式匹配下的回退问题，时间复杂度仅为O（n）。
AC自动机的构建
1.构建Trie（字典树）
和正常的Trie结构相比，AC自动机的字典树结构中多了一个fail指针。
C语言模板（仅包含26个小写字母的字典树）；
struct Node{
Node *son[26];
Node *fail;
int cnt;
Node(){
for(int i=0;i<26;i++){
son[i]=NULL;
}
fail=NULL;
cnt=0;
}
BuildTree(const char* str){
Node *now=this;
int len=strlen(str);
for(int i=0;i<len;i++){
int num=str[i]-'a';
if(now->son[num]==NULL){
now->son[num]=new Node();
}
now=now->son[num];
}
now->cnt=1;
}
} *p[MAX_L];
2.fail数组的构建
void BuildAC(){
int head,tail;
head=0;tail=0;
Node *now;
Node *f;
p[head++]=root;
while(head!=tail){
now=p[tail++];
if(now==root){
for(int i=0;i<26;i++){
if(now->son[i]!=NULL)
{
now->son[i]->fail=root;
p[head++]=now->son[i];
}
}
}else{
for(int i=0;i<26;i++){
f=now->fail;
if(now->son[i]!=NULL){
while(f!=NULL && f->son[i]==NULL){
f=f->fail;
}
if(f==NULL)
now->son[i]->fail=root;
else
{
now->son[i]->fail=f->son[i];
}
p[head++]=now->son[i];
}
}
}
}
}
模板
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAX_L=500500;
const int MAX_N=10050;
const int MAX_M=1000050;
struct Node{
Node *son[26];
Node *fail;
int cnt;
Node(){
for(int i=0;i<26;i++){
son[i]=NULL;
}
fail=NULL;
cnt=0;
}
BuildTree(const char* str){
Node *now=this;
int len=strlen(str);
for(int i=0;i<len;i++){
int num=str[i]-'a';
if(now->son[num]==NULL){
now->son[num]=new Node();
}
now=now->son[num];
}
now->cnt++;
}
Show(){
for(int i=0;i<26;i++){
if(this->son[i]!=NULL)
{
printf("%c",'a'+i);
this->son[i]->Show();
}
}
}
} *p[MAX_L];
char s[MAX_M];
char d[50];
Node * root;
void BuildAC(){
int head,tail;
head=0;tail=0;
Node *now;
Node *f;
p[head++]=root;
while(head!=tail){
now=p[tail++];
if(now==root){
for(int i=0;i<26;i++){
if(now->son[i]!=NULL)
{
now->son[i]->fail=root;
p[head++]=now->son[i];
}
}
}else{
for(int i=0;i<26;i++){
f=now->fail;
if(now->son[i]!=NULL){
while(f!=NULL && f->son[i]==NULL){
f=f->fail;
}
if(f==NULL)
now->son[i]->fail=root;
else
{
now->son[i]->fail=f->son[i];
}
p[head++]=now->son[i];
}
}
}
}
}
int SearchS(const char* str){
int ans=0;
int len=strlen(str);
Node *now=root;
Node *tmp;
for(int i=0;i<len;i++)
{
while(now!=NULL&&now->son[str[i]-'a']==NULL){
now=now->fail;
}
if(now==NULL)
now=root;
if(now->son[str[i]-'a']!=NULL){
now=now->son[str[i]-'a'];
tmp=now;
while(tmp!=root&&tmp->cnt!=-1){
ans+=tmp->cnt;
tmp->cnt=-1;
tmp=tmp->fail;
}
}
}
return ans;
}
int main(){
int m,n,ans;
scanf("%d",&m);
while(m--){
root=new Node();
scanf("%d",&n);
while(n--){
scanf("%s",d);
root->BuildTree(d);
}
scanf("%s",s);
BuildAC();
ans=SearchS(s);
printf("%d\n",ans);
}
return 0;
}
