hdu 2896 AC自動機

算是AC自動機裡面的裸題吧 可惡的re了幾次 看清題目 沒說是由小寫字母構成 ， 所以next得開到127 考慮到所有的字符才行， 注意不能算重復那裡我用了一個變量flash來標記每次查找是否走過 如果flash=當前編號的網站 則是走過，，其它也沒啥了

#include
#include
#include
#include
#include
#include
using namespace std;

struct node
{
    node *fail;
    node *next[127];
    int flash;
    int cont;
    int id;
}*a,*b,*root;
char word[20010];
int num[1010],print[1100][1010];
int keytree(char str[],int k)
{
    int len=strlen(str);
    node *p,*q;
    p=root;
    for(int i=0;i<len;i++)
    {
        if(p->next[str[i]-32]!=NULL)
        p=p->next[str[i]-32];
        else 
        {
            q=(struct node*)malloc(sizeof(struct node));
            memset(q,NULL,sizeof(struct node));
            p->next[str[i]-32]=q;
            p=q;
        }
    }    
    p->cont++;
    p->id=k;
    return 0;
}
int make_fail()
{
    queue<node*>Q;
    root->fail=NULL;
    a=root;
    Q.push(a);
    while(!Q.empty())
    {
        b=Q.front();
        Q.pop();
        for(int i=0;i<127;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 k)
{
    int len=strlen(str);
    int sum=0;
    struct node *p,*q;
    p=root;
    for(int i=0;i<len;i++)
    {
        while(p->next[str[i]-32]==NULL&&p!=root) p=p->fail;
        p=p->next[str[i]-32];
        if(p==NULL) p=root;
        q=p;
        while(q->flash!=k&&q!=root)
        {
            if(q->cont)
            {
                sum++;
                num[sum]=q->id;
            }
            q->flash=k;
            q=q->fail;
        }
    }
    return sum;    
}
int main()
{
    int n,i,j;
    char str[500];
    scanf("%d",&n);
    getchar();
    root=(struct node*)malloc(sizeof(struct node));
    memset(root,NULL,sizeof(struct node));
    for(i=1;i<=n;i++)
    {
        gets(str);
        keytree(str,i);
    }
    make_fail();
    int m;
    int x=0;
    int t;
    int number[1100];
    scanf("%d",&m);
    getchar();
    for(i=1;i<=m;i++)
    {
        gets(word);
        t=find(word,i);
        if(t)
        {
            sort(num+1,num+1+t);
            x++;
            number[x]=i;
            print[x][0]=t;
            for(j=1;j<=t;j++)
            print[x][j]=num[j];
        }
    }
    for(i=1;i<=x;i++)
    {
        printf("web %d:",number[i]);
        for(j=1;j<=print[i][0];j++)
        printf(" %d",print[i][j]);
        printf("\n");
    }
    printf("total: %d\n",x);
    return 0;
}