Keywords Search

一道AC自动机的模板题，但是第一次敲真是苦逼。。

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

const int alphabet = 26;
struct node
{
    node* branch[alphabet];
    node* fail;
    int count;
    node()
    {
        for(int i=0; i<alphabet; i++)
            branch[i] = NULL;
        fail = NULL;
        count = 0;
    }
};

void dictionary(node* root, char word[])
{
    node* p = root;
    int k, i=0;
    while(word[i])
    {
        k = word[i] - 'a';
        if(p->branch[k] == NULL)
            p->branch[k] = new node();
        p = p->branch[k];
        i++;
    }
    p->count++;
}

void build_fail(node* root)
{
    node* p;
    node* f;
    queue<node*> Q;
    root->fail = NULL;
    Q.push(root);
    while(!Q.empty())
    {
        p = Q.front(); Q.pop();
        for(int i=0; i<alphabet; i++)
        {
            if(p->branch[i] != NULL)
            {
                f = p->fail;
                while(f!=NULL)
                {
                    if(f->branch[i] != NULL)
                    {
                        p->branch[i]->fail = f->branch[i]; 
                    break;
                    }
                    f = f->fail;
                }
                if(f==NULL) p->branch[i]->fail = root;
                Q.push(p->branch[i]);
            }
        }
    }
}

int search(node* root, char str[])
{
    int k, i=0, sum=0;
    node* p = root;
    node* temp;
    while(str[i])
    {
        k = str[i] - 'a';
        while(p->branch[k] == NULL && p!=root)
            p = p->fail;
        if(p->branch[k]!=NULL) p = p->branch[k];
        else p = root;
        temp = p;
        while(temp!=root && temp->count!=-1)
        {
            sum += temp->count;
            temp->count = -1;
            temp = temp->fail;
        }
        i++;
    }
    return sum;
}

int main()
{
    int c, n;
    char word[55], str[1000005];
    cin >> c;
    while(c--)
    {
        node* root = new node();
        cin >> n;
        while(n--)
        {
            scanf("%s", &word);
            dictionary(root, word);
        }
        build_fail(root);
        scanf("%s", &str);
        cout << search(root, str) << endl;
    }
    return 0;
}