病毒侵袭持续中---hdu3065（AC自动机模板）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3065

模板题，没什么好说的。。。

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

const int N = 2e6+10;

int a[1100];
char virus[1100][55], MumStr[N];

struct node
{
    int leaf;
    node *next[26],*fail;
};

void AddTrie(char s[], node *root, int num)
{
    node *p = root;
    for(int i=0; s[i]; i++)
    {
        int k = s[i]-'A';
        if(p->next[k]==NULL)
            p->next[k] = new node();
        p = p->next[k];
    }
    p->leaf = num;
}
void GetFail(node *root)
{
    node *p, *q;
    queue<node*>Q;
    Q.push(root);
    while(Q.size())
    {
        p = Q.front();
        Q.pop();
        for(int i=0; i<26; i++)
        {
            if(p->next[i]!=NULL)
            {
                q = p->fail;
                while(q!=NULL)
                {
                    if(q->next[i]!=NULL)
                    {
                        p->next[i]->fail = q->next[i];
                        break;
                    }
                    q = q->fail;
                }
                if(q == NULL)
                    p->next[i]->fail = root;
                Q.push(p->next[i]);
            }
        }
    }
}
void Query(node *root)
{
    node *p = root, *q;
    for(int i=0; MumStr[i]; i++)
    {
        if(MumStr[i]<'A' || MumStr[i]>'Z')///如果是其他字符的话直接回到root；
        {
            p = root;
            continue;
        }
        int k = MumStr[i]-'A';
        while(p->next[k]==NULL && p!=root)
            p = p->fail;
        p = p->next[k];
        if(p==NULL)
            p = root;
        q = p;
        while(q!=root)
        {
            if(q->leaf)
                a[q->leaf]++;
            q = q->fail;
        }
    }
}
void FreeTrie(node *root)
{
    node *p = root;
    for(int i=0; i<26; i++)
    {
        if(p->next[i]!=NULL)
            FreeTrie(p->next[i]);
    }
    free(p);
}
int main()
{
    int n;
    while(scanf("%d", &n)!=EOF)
    {
        node *root = new node();
        for(int i=1; i<=n; i++)
        {
            scanf("%s", virus[i]);
            AddTrie(virus[i], root, i);
        }
        GetFail(root);
        scanf("%s", MumStr);
        memset(a, 0, sizeof(a));
        Query(root);
        for(int i=1; i<=n; i++)
        {
            if(a[i])
                printf("%s: %d
", virus[i], a[i]);
        }
        FreeTrie(root);
    }
    return 0;
}
/*
3
ABBA
BB
AB
AABBA
*/