前言
为了写一个AC自动机模板，参考了n多blog的代码，不料所有代码都如出一辙。本想写一个风格独特的模板，至少与其他人的不一样，但是因为思路上的先入为主等原因，还真没写出什么花样，跟网上其他的模板也没什么不同。
题目大意
给出n个模式串和一个被匹配串，问有多少个模式串可以成功匹配。
思路
裸AC自动机，模板题。思路见代码。
代码
#include
#include
using namespace std;
#define T_SIZE 1000000
#define P_SIZE 50
#define TOTAL_P 10000
struct trie
//利用结构体来封装字典树的节点。
{
trie* next[26];
trie* fail;
int num;
trie()
//构造函数。
{
for(int i=0;inext[s[i]-'a']==NULL)
p->next[s[i]-'a']=new trie;
p=p->next[s[i]-'a'];
}
p->num++;
}
void build_ac_automation(trie* root)
//利用广搜构建失败指针
{
int head=0,tail=0;
q[tail++]=root;
while(head!=tail)
{
trie* front=q[head++];
//front为队头元素
for(int i=0;inext[i]!=NULL)
//遍历队头元素的子节点
{
trie* p=front->fail;
while(p!=NULL)
//只有根节点的失败指针为NULL
{
if(p->next[i]!=NULL)
//顺着失败指针往回走，直至某个节点，其拥有一个字母为'a'+i的子节点。
{
front->next[i]->fail=p->next[i];
break;
}
p=p->fail;
}
if(p==NULL)
//p==NULL说明顺着失败指针往回走的过程中没有找到合适的节点，所以将失败指针指向根节点。
front->next[i]->fail=root;
q[tail++]=front->next[i];
}
}
}
int ac_find(trie* root,char* T)
{
trie* p=root;
int sum=0;
for(int i=0,len=strlen(T);inext[T[i]-'a']==NULL&&p!=root)
//若当前节点的没有一个字符为T[i]的儿子且当前节点不是根节点
//通俗的讲，就是顺着失败指针往回走，直至找到合适的节点或根节点为止。
p=p->fail;
if(p->next[T[i]-'a']!=NULL)
//p->next[T[i]-'a']==NULL说明没找到合适的节点，p指针指在根节点上。
p=p->next[T[i]-'a'];
trie* temp=p;
while(temp!=root&&temp->num!=-1)
//顺着失败指针往回走，一直到根节点。
{
sum+=temp->num;
//若当前节点的num不为0，则说明以当前节点字母结尾的单词出现过一次。
//此单词是以上一次循环的节点单词为结尾的单词的子集。
temp->num=-1;
//标记num为-1，避免重复计算。
temp=temp->fail;
}
}
return sum;
}
int main()
{
int t;
for(scanf("%d",&t);t>0;t--)
{
trie* root=new trie;
int n;
scanf("%d",&n);
getchar();
for(int i=0;i<n;i++)
{
gets(P);
insert(root,P);
}
build_ac_automation(root);
gets(T);
printf("%d\n",ac_find(root,T));
}
}