Keywords Search(AC自动机)

原题链接
先用指针建一个字典树，再用BFS更新fail指针，匹配的时候要保证一个单词只被记录一次，所以当一个单词计数了以后，尾节点要清零。动态内存分配能节约空间，而且代码也容易理解。
还有一点要注意的是，结构体一定要写构造方法，不然new的时候会发生段错误
注意：用完字典树，记得回收内存。

#include<cstdio>
#include<queue>
using namespace std;
const int MAXN=1e6+5;
struct Node
{
    int cnt;
    Node *fail;
    Node *next[26];
    Node()
    {
        cnt=0;
        fail=NULL;
        for(int i=0;i<26;i++) next[i]=NULL;
    };
};
char s[MAXN];
void Build_trie(Node *root,const char *keyword)
{
    Node *p=root;
    for(int i=0;keyword[i];i++)
    {
        int v=keyword[i]-'a';
        if(p->next[v]==NULL) p->next[v]=new Node;
        p=p->next[v];
    }
    p->cnt++;
}
void Build_AC_automation(Node *root)
{
    queue<Node*> que;
    que.push(root);
    while(!que.empty())
    {
        Node *cur=que.front();
        que.pop();
        for(int i=0;i<26;i++)
        {
            if(cur->next[i]!=NULL)
            {
                Node *p=cur->fail;
                while(p!=NULL)
                {
                    if(p->next[i]!=NULL)
                    {
                        cur->next[i]->fail=p->next[i];
                        break;
                    }
                    p=p->fail;
                }
                if(p==NULL) cur->next[i]->fail=root;
                que.push(cur->next[i]);
            }
        }
    }
}
int match(Node *root)
{
    int cnt=0;
    Node *p=root;
    for(int i=0;s[i];i++)
    {
        int v=s[i]-'a';
        while(p!=NULL&&p->next[v]==NULL) p=p->fail;
        if(p==NULL)
        {
            p=root;
            continue;
        }
        p=p->next[v];
        Node *tmp=p;
        while(tmp!=root)
        {
            if(tmp->cnt)
            {
                cnt+=tmp->cnt;
                tmp->cnt=0;
            }
            else break;
            tmp=tmp->fail;
        }
    }
    return cnt;
}
void delete_all(Node *root)
{
    queue<Node*> que;
    que.push(root);
    while(!que.empty())
    {
        Node *cur=que.front();
        que.pop();
        for(int i=0;i<26;i++)
        {
            if(cur->next[i]!=NULL)
            {
                que.push(cur->next[i]);
            }
        }
        delete(cur);
    }
}
int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        Node *root=new Node;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            char keyword[55];
            scanf("\n%s",keyword);
            Build_trie(root,keyword);
        }
        Build_AC_automation(root);
        scanf("\n%s",s);
        printf("%d\n",match(root));
        delete_all(root);
    }
    return 0;
}