Description
给出由若干单词组成的字典（可能有相同的单词），再给出一篇文章（一个字符串），请计算有多少个不同的单词在字符串中出现。
Input
第1行一个正整数N。表示字典中单词的数目。接下来的N行，每行一个字符串（长度不超过50），表示一个单词。最后一行为一个长字符串（长度不超过100000）。注意：单词和字符串均由小写字母构成。
Output
一行一个整数，表示长字符串中包含单词的数量。
Hint
N<=40000
Solution
AC自动机其实就是kmp+trie树（但实际上我觉得并没有kmp代码基本上还是按照trie树来的。。。），然后大概就是先把每个模式串按照前缀存进trie树，然后，，，，setnext数组，我是把next放进结构体里面存的所以还行，然后最后dofind的过程就是用主串来匹配模式串构成的trie树，然后就完了，，，挺好理解的就是代码写着令人智熄。。
注意事项：
1、newp要初始化成1因为是从1结点开始存的，0结点在setnext的过程中要用。不初始化会爆。。。
2、然后为了防止比如
abc
ab
这种情况的时候如果就这样读的话读abc这个串的时候会读一个b标记的end_line和c标记的end_line，就已经把ab这个前缀读了，再读ab的话会重复，所以在cnt+=tree[k].end_line之后就把end_line给赋值为false就会防止读重复的情况了。
3、我是傻逼。。。数组要开到两百万我又只开了四万结果RE了一半。。有毒啊拉低我正确率我嚓本来我能一遍AC的。。。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define maxm 27
#define maxn 2000005
using namespace std;
struct Trie{
int ch[maxm];
bool end_line;
int next;
}tree[maxn];
int newp=1,n,cnt;
char tmp[maxn],S[maxn];
void insert(char *s){
int x=1,lenofS=strlen(s+1);
for(int i=1;i<=lenofS;i++){
int y=s[i]-'a';
if(tree[x].ch[y]==0){
tree[x].ch[y]=++newp;
}
x=tree[x].ch[y];
}
tree[x].end_line=true;
}
void setnext(){
for(int i=0;i<26;i++){
tree[0].ch[i]=1;
}
queue<int>q;
q.push(1);
tree[1].next=0;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<26;i++){
if(tree[u].ch[i]==0){
tree[u].ch[i]=tree[tree[u].next].ch[i];
}
else{
q.push(tree[u].ch[i]);
int v=tree[u].next;
tree[tree[u].ch[i]].next=tree[v].ch[i];
}
}
}
}
void dofindkmp(){
int u=1,lenofS=strlen(S+1);
for(int i=1;i<=lenofS;i++){
int c=S[i]-'a';
int k=tree[u].ch[c];
while(k>1){
cnt+=tree[k].end_line;
tree[k].end_line=false;
k=tree[k].next;
}
u=tree[u].ch[c];
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",tmp+1);
insert(tmp);
}
scanf("%s",S+1);
setnext();
dofindkmp();
printf("%d
",cnt);
return 0;
}