题目大意：给定一些单词和一个字符串，求有多少单词在字符串中出现过
首先我不想吐槽题号。真的不想。真的不想！！别问我为什么说这句话！！不想就是了！！
AC自动机模板题
简单介绍一下AC自动机
首先不要把这东西和自动AC机弄混 自动AC机算法等我们发明之后再加介绍
这东西的实现方法就是把所有单词插入一棵Trie树 然后在Trie树上跑KMP算法
每个节点有一个next指针 和KMP算法中的next一样 指向最长公共前后缀所代表的节点上 不存在指向root
匹配的时候每匹配到一个节点时，将该节点、该节点的next节点、该节点的next节点的next节点……直到root为止的单词数全都加到ans上，然后清零(防止重复计数)
具体见 http://blog.csdn.net/niushuai666/article/details/7002823
这题卡内存，开动态的不用想了，开静态的可以考虑将内存恰好压到32768KB，我卡了32132KB过去的。。。。。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct Trie{
char letter;
int next,fa;
int cnt;
int sons[26];
}tree[260200];
int tot,root;
char s[1001001];
int n,ans;
void insert(int &p,char *pos,int from)
{
int num=(*pos)-'a';
if(!p)
{
p=++tot;
tree[p].fa=from;
tree[p].letter=*(pos-1);
}
if(!*pos)
{
tree[p].cnt++;
return ;
}
insert(tree[p].sons[num],pos+1,p);
}
int q[65540];
unsigned short r,h;
void bfs()
{
int i,temp;
q[++r]=root;
while(r!=h)
{
int p=q[++h];
if(tree[p].fa==root)
tree[p].next=root;
else
{
temp=tree[tree[p].fa].next;
while( temp!=root && !tree[temp].sons[tree[p].letter-'a'] )
temp=tree[temp].next;
if( tree[temp].sons[tree[p].letter-'a'] )
temp=tree[temp].sons[tree[p].letter-'a'];
tree[p].next=temp;
}
for(i=0;i<26;i++)
if(tree[p].sons[i])
q[++r]=tree[p].sons[i];
}
}
void Aho_Corasick_Automation(int p,char *pos)
{
int temp;
for(;*pos;pos++)
{
while( p!=root && !tree[p].sons[(*pos)-'a'] )
p=tree[p].next;
if(tree[p].sons[(*pos)-'a'])
{
p=tree[p].sons[(*pos)-'a'];
for(temp=p;temp!=root;temp=tree[temp].next)
ans+=tree[temp].cnt,tree[temp].cnt=0; }
}
}
void initialize()
{
memset(tree,0,sizeof tree);
root=tot=ans=0;
}
int main()
{
int i,T;
for(cin>>T;T;T--)
{
initialize();
cin>>n;
for(i=1;i<=n;i++)
{
scanf("%s",s+1);
insert(root,s+1,1);
}
bfs();
scanf("%s",s+1);
Aho_Corasick_Automation(root,s+1);
cout<<ans<<endl;
}
}