都说这是道ac自动机模板题     也是我的第一道    感觉学起来还行   先把kmp和字典树学号了再学这个应该不难吧！！！！！  看了好多网上在构造失败指针都时候用数组模拟bfs了   我这里还是用到了队列函数（自己感觉简单点） 

#include<stdio.h>
#include<string.h>
#include<queue>
#include<malloc.h>
#include<iostream>
using namespace std;

struct node
{
    node *fail;
    node *next[26];
    int cont;
}*a,*b,*root;
char text[1000010];
int keytree(char str[])
{   
    int len=strlen(str);
    int i;
    struct node *p,*q;
    p=root;
    
    for(i=0;i<len;i++)
    {    
        if(p->next[str[i]-‘a‘]!=NULL)
        p=p->next[str[i]-‘a‘];
        else 
        {
            q=(struct node*)malloc(sizeof(struct node));
            memset(q,NULL,sizeof(struct node));
            p->next[str[i]-‘a‘]=q;
            p=q;
        } 
    }
    p->cont++;
    return 0;
}
int makefail()
{
    queue<node*>Q;
    root->fail=NULL;
    a=root;
    Q.push(a);
    
    while(!Q.empty())
    {
        b=Q.front();
        Q.pop();
        for(int i=0;i<26;i++)
        {
            if(b->next[i]!=NULL)
            {
                if(b==root)
                {  
                    b->next[i]->fail=root;
                }
                else
                {  
                    a=b->fail;
                    while(a!=NULL)
                    {
                        if(a->next[i]!=NULL) 
                        {
                            b->next[i]->fail=a->next[i];
                            break;
                        }
                        a=a->fail;
                    }
                    if(a==NULL) b->next[i]->fail=root;
                }
                Q.push(b->next[i]);
            }
        }
    }
    return 0;
}

int find(char str[])
{   
    int len=strlen(str);
    int i;
    int sum=0;
    struct node *p,*q;
    p=root;
    for(i=0;i<len;i++)
    {
        while(p->next[str[i]-‘a‘]==NULL&&p!=root) p=p->fail;
        p=p->next[str[i]-‘a‘];
        if(p==NULL) p=root;
        q=p;
        while(q->cont!=-1&&q!=root)
        {    
            sum+=q->cont;
            q->cont=-1;
            q=q->fail;
        }
    }
    return sum;    
}
int clear(node *p)
{
    int i;
    for(i=0;i<26;i++)
    {
        if(p->next[i]!=NULL) clear(p->next[i]);
    }
    free(p);
    return 0;
}
int main()
{
    int T,i,j,n;
    char word[100];
    scanf("%d",&T);
    while(T--)
    {
        root=(struct node*)malloc(sizeof(struct node));
        memset(root,NULL,sizeof(struct node));
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%s",word);
            keytree(word);
        }
        makefail();
        scanf("%s",text);
        printf("%d\n",find(text));
        clear(root);
    }
    return 0;
}

hdu 2222 AC自动机