AC自动机

#include <cstdio>
#include <cstring>

const int MAXPT=500007;   //最大节点数
const int size=26;     //子节点数
const char start=‘a‘;  //子节点标号对应关系
 
class Ac_Automat
{
private:
    struct Node
    {
        Node *fail;
        Node *next[size];
        int cnt;    //各种用途:计数,标号等
        bool flag;   //是否为单词结束
        void newnode () //生成节点
        {
            fail=NULL;
            for (int i=0;i<size;i++)
                next[i]=NULL;
            cnt=0;
            flag=false;
        }
    };
    
    Node *q[MAXPT],H[MAXPT],*root;
    int fr,tl,t;
public:
    void Init ()
    {
        fr = tl = 0;
        t = 0;
        H[t].newnode();
        root = &H[t++];
    }

    void Insert (char *s)
    {
        int len = strlen(s);
        Node *p = root;
        for (int i=0;i<len;i++)
        {
            int k = s[i] - start;
            if (p->next[k] == NULL)
            {
                H[t].newnode();
                p->next[k] = &H[t++];
            }
            p = p->next[k];
        }
        p->cnt++;
        p->flag=true;
    }

    void Build ()
    {
        root->fail = NULL;
        q[tl] = root;
        while (fr <= tl)
        {
            Node *tmp = q[fr++];
            Node *p = NULL;
            for (int i=0;i<size;i++) if (tmp->next[i])
            {
                if (tmp == root)
                    tmp->next[i]->fail = root;
                else
                {
                    p = tmp->fail;
                    while (p != NULL)
                    {
                        if (p->next[i])
                        {
                            tmp->next[i]->fail = p->next[i];
                            break;
                        }
                        p = p->fail;
                    }
                    if (p == NULL) 
                        tmp->next[i]->fail = root;
                }
                q[++tl] = tmp->next[i];
            }
        }
    }
    
    int Query (char *s)
    {
        int res = 0;
        Node *p = root;
        int len = strlen(s);
        for (int i=0;i<len;i++)
        {
            int k = s[i] - start;
            while (p->next[k] == NULL && p != root)
                p = p->fail;
            
            p = p->next[k];
            if (p == NULL) p = root;
            Node *tmp = p;
            while (tmp != root && tmp->cnt != -1)  //随查询要求不同而修改
            {
                res += tmp->cnt;
                tmp->cnt = - 1;
                tmp = tmp->fail;
            }
        }
        return res;
    }
}ac;

char str[1000005],s[55];

int main ()
{
    int T,i,n;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d",&n);
        ac.Init();
        for (i=1;i<=n;i++)
            scanf("%s",s),ac.Insert(s);
        scanf("%s",str);
        ac.Build();
        printf("%d\n",ac.Query(str));
    }
    return 0;
}