AC自动机

#include<iostream>
#include<algorithm>
#include<queue>
#include<string.h>
#include<stdlib.h>

using namespace std;

#define MAX_N 1000006
#define MAX_Tot 500005

struct ACo{
    struct state{
        //子節點數組 
        int next[26];
        //當前節點的失敗指針 
        int fail;
        //到當前位置的字符串結束個數 
        int cnt;
        
    }stateTable[MAX_Tot];
    
    //當前AC自動機樹的節點個數 
    int size; 
    queue<int> que;
    //初始化 
    void init()
    {
        //將節點初始化 
        while(que.size()) que.pop();
        for(int i=0;i<MAX_Tot;i++)
        {
            memset(stateTable[i].next,0,sizeof(stateTable[i].next));
            stateTable[i].fail = 0;
            stateTable[i].cnt = 0; 
        }
        //根節點一定存在，所以節點個數爲1 
        size = 1;
    } 
    
    //構建字典樹 
    void insert(char *str)
    {
        int n = strlen(str);
        int now = 0;
        for(int i=0;i<n;i++)
        {
            char c = str[i];
            //如果到當前節點子節點不存在的話 
            if(!stateTable[now].next[c-'a'])
            {
                //開闢新節點，並將節點個數加一，注意size從1開始的 
                stateTable[now].next[c-'a'] = size++;
            }    
            //每次都要進行走到下一節點 
            now = stateTable[now].next[c-'a'];
            
        } 
        //該字符串便利完之後走到的節點 
        stateTable[now].cnt++;
    } 
    //構造失配指針 
    void build()
    {
        
        //根節點的失配指針設爲-1 
        stateTable[0].fail = -1;
        //將根節點壓入隊列 
        que.push(0);
        
        while(que.size())
        {
            //取當前隊列中的第一個，即廣度優先遍歷數，保證每層節點的失敗指針都選擇完成，纔有可能繼續下一層
            //否則，如果深度優先遍歷會導致指針不爲最優，因爲別的叉沒有被構造。 
            int u = que.front();
            //取一個，要將其彈出 
            que.pop();
            
            //將當前節點的所有子節點遍歷 
            for(int i=0;i<26;i++)
            {
                //如果當前節點的子節點之一存在子節點 
                if(stateTable[u].next[i])
                {
                    //判斷當前點是否爲根節點 
                    if(u==0)
                    {
                        //如果爲根節點，沒辦法，只能讓當前節點的子節點的失敗指針指向0，即指向根節點 
                        //根節點的第一層節點都滿足，可以想一下。 
                        stateTable[stateTable[u].next[i]].fail = 0;
                    }
                    //否則 
                    else
                    {
                        //記錄當前節點的失敗指針 
                        int v = stateTable[u].fail;
                        //如果失敗指針存在的話 
                        while(v!=-1)
                        {
                            //並且其失敗指針節點也存在子節點 
                            if(stateTable[v].next[i])
                            {
                                //將當前節點 的 失敗指針 指向其 失敗指針節點 的下一個節點 
                                stateTable[stateTable[u].next[i]].fail = stateTable[v].next[i] ;
                                break;
                            }
                            //記錄下失敗指針的位置。 
                            v = stateTable[v].fail; 
                        }
                        //如果找了半天，其各種祖先節點的失敗指針仍然不存在 
                        if(v==-1)
                        {
                            //只能將當前節點的失敗指針指向根節點 
                            stateTable[stateTable[u].next[i]].fail = 0;
                        }
                    }
                    //將當前節點入隊列，畢竟要廣搜一層來確定 
                    que.push(stateTable[u].next[i]);
                }
            }
        }
        
    }
    int Get(int u)
    {
        int res = 0;
        while(u)
        {
            //當前節點的不爲根節點
            //res+上當前節點下的單詞數 
            res = res+stateTable[u].cnt;
            //當前節點單詞數清零，避免一條子樹下重複加值 
            stateTable[u].cnt = 0;
            //回溯其失敗指針下滿足條件的單詞數 
            u = stateTable[u].fail;
        }
        return res;
    }
    //製造匹配函數 
    int match(char *S)
    {
        int n = strlen(S);
        int res = 0,now = 0;
        for(int i=0;i<n;i++)
        {
            char c = S[i];
            //存在自不必多說，向下一個指針移動 
            if(stateTable[now].next[c-'a'])
            {
                now = stateTable[now].next[c-'a']; 
            }
            else
            {
                //一旦失配，不回溯根節點，而是回溯失敗指針節點 
                int p = stateTable[now].fail;
                //如果失配指針存在，或者失配指針指向的根節點存在 
                while(p!=-1 && stateTable[p].next[c-'a']==0)
                {
                    //更新失敗指針的位置，即不=停的向父節點靠攏 
                    p = stateTable[p].fail;
                }
                //如果只能找到根節點，那就從根節點進行匹配 
                if(p==-1)
                {
                    now = 0;
                }
                else{
                    //不然，當前節點跳到失敗節點的存在子節點 
                    now = stateTable[p].next[c-'a'];
                }
            }
            //如果當前節點下存在的單詞數不爲0 
            if(stateTable[now].cnt)
            {
                //記錄到當前節點爲止所有含有的父節點（失敗節點）的單詞數， 
                res +=Get(now);
            }
        }
        return res;
    }
}aho;
int T;
int n;
char S[MAX_N];

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        aho.init();
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%s",S);
            aho.insert(S);
        }
        aho.build();
        scanf("%s",S);
        printf("%d
",aho.match(S));
    }
 }