本质我认为应该是树（trie树）上kmp 参考http://www.cppblog.com/mythit/archive/2009/04/21/80633.html 网上很多的教程都是看了他的博客或借鉴而来的 第一部分建trie树 将字符串一位一位的加进去 如果这个字符为NULL则加一个指针将头指针指向这个点继续操作 插入完成之后我们给最后一个点的count+1（相当于只有是匹配串的末尾才计数）（刚开始没听懂的时候老觉得AC自动机或是trie图有漏洞）
第二部分fail指针 第一层入队 逐层入队 考虑入队后的一个点 去找他父亲的fail指针下的点(即将要出队的点的fail->)有没有指向自己的next指针 如果有就将fail指针指向他否则指向他父亲的fail指针下的点 如果没有就继续fail的跳fail直到跳到根节点如果还没有就结束（！并不建议这么写有些问题可以将边界条件变成NULL） 思想可以类比kmp的next数组的推法 tail++ …… 考虑一要出队的点
按字典序进行上述操作 当不是NULL的指针都遍历了一次之后 head++
root为现在要出队的点 实际只需要不断的出队 当出队时会有新的字符补进来 如果head=tail则必然所有的点都标了fail指针 特别地有，当root出队时即第一个点出队时所有的子节点的fail指针必然指向root 所以让root的指针指向自己可以符合上述操作的一致性（如果上面出队判断为跳到NULL则root的fail应指向NULL这种写法较简单）
第三部分 查询 如果这个字符匹配那么继续匹配（看next指针是不是NULL） 如果这个字符的count不是1即不是末尾 如果是就加 否则沿fail的指针继续匹配
上代码
#include<bits/stdc++.h> using namespace std; const int kind=26; char str[1000005]; char keyword[51]; struct node{ node *fail; node *next[kind]; int count; node(){ fail=NULL; count=0; memset(next,NULL,sizeof(next)); } }*q[500001]; int head,tail; void insert(char *str,node *root){ node *p=root; int i=0,index; while(str[i]){ index=str[i]-'a'; if(p->next[index]==NULL) p->next[index]=new node(); p=p->next[index]; i++ ; } p->count++; } void build_fail(node *root){ int i; root->fail=NULL; q[head++]=root; while(head!=tail){ node *temp=q[tail++]; node *p=NULL; for(int i=0;i<26;i++){ if(temp->next[i]!=NULL){ if(temp==root) temp->next[i]->fail=root; else{ p=temp->fail; while(p!=NULL){ if(p->next[i]!=NULL){ temp->next[i]->fail=p->next[i]; break; } p=p->fail; } if(p==NULL) temp->next[i]->fail=root; } q[head++]=temp->next[i]; } } } } int query(node *root){ int i=0,index,cnt=0,len=strlen(str); node *p=root; while(str[i]){ index=str[i]-'a'; while(p->next[index]==NULL&&p!=root) p=p->fail; p=p->next[index]; if(p==NULL) p=root; node *temp=p; while(temp!=root&&temp->count!=-1){ cnt+=temp->count; temp->count=-1; temp=temp->fail; } i++; } return cnt; } int main() { int n,t; scanf("%d",&t); while(t--){ head=tail=0; node *root=new node(); scanf("%d",&n); getchar(); while(n--){ gets(keyword); insert(keyword,root); } build_fail(root); scanf("%s",str); printf("%d\n",query(root)); } return 0; }