/*
     啥也不说了，直接套模板。。。
  */
  1 #include<iostream>   2 #include<map>  3 #include<string>   4 #include<cstring>   5 #include<queue>   6 #define N 500000  7 using namespace std;  8   9 class AC_Atomata 10 { 11 public: 12   int nodeN;//trie树的节点个数  13   int trie[N][26];//trie树  14   int f[N];//失配函数  15   //map<string, int>ms;//字符串到字符串编号的映射，防止出现多个字符串的模板 16   int last[N];// last[j]表示节点j沿着失配指针往回走时遇到的下一个单词节点的编号 17   int cnt;//最多在主串中出现的单词数  18   int val[N];//标记该节点是否为字符串的端点，该题中val[j]表示以节点j所对应的字符所结束的相同字符串的个数 19   int vis[N];//标记该节点已经访问过了  20   queue<int>q; 21   void init(); 22   void buildTrie(char *p); 23   void getFail(); 24   void find(char *T); 25   void countWords(int k); 26 }; 27  28 void AC_Atomata::init() 29 { 30    nodeN=0;  31    ms.clear(); 32    memset(vis, 0, sizeof(vis)); 33    memset(trie[0], 0, sizeof(trie[0])); 34    //memset(cnt, 0, sizeof(cnt)); 35    cnt=0; 36 }  37  38 void AC_Atomata::buildTrie(char *p) 39 { 40    int i, u=0; 41    for(i=0; p[i]; ++i) 42    { 43       int k=p[i]-‘a‘; 44       if(!trie[u][k]) 45       { 46             memset(trie[nodeN+1], 0, sizeof(trie[nodeN+1])) ; 47           trie[u][k]=++nodeN; 48           val[nodeN]=0; 49       } 50       u=trie[u][k]; 51    }  52    ++val[u]; 53    //ms[string(p)]=v; 54 } 55  56 void AC_Atomata::getFail() 57 { 58    int u, v, r, c; 59    while(!q.empty())  q.pop(); 60    f[0]=0; 61    for(c=0; c<26; ++c) 62    { 63        u=trie[0][c]; 64        if(u) 65        { 66              f[u]=0; 67              q.push(u); 68              last[u]=0; 69        } 70    } 71    while(!q.empty()) 72    { 73         r=q.front(); 74         q.pop(); 75         for(c=0; c<26; ++c) 76     { 77         u=trie[r][c]; 78         if(!u) continue; 79         q.push(u); 80         v=f[r]; 81         while(v && !trie[v][c])  v=f[v]; 82         f[u]=trie[v][c]; 83         last[u]=val[f[u]] ? f[u] : last[f[u]]; 84     }  85    } 86 }  87  88 void AC_Atomata::countWords(int k) 89 { 90    if(k && !vis[k]) 91    { 92        //++cnt[val[k]];//k就是该单词所对应的最后一个字符的节点编号，val[k]是这个单词再输入时候的编号 93        vis[k]=1;//表示以该节点结束的字符串已经访问过了，如果主串中再出现该字符串则不会再计算在内 94        cnt+=val[k];//  95        countWords(last[k]); 96    } 97 } 98  99 void AC_Atomata::find(char *T) 100 {101    int i, j;102    for(i=0, j=0; T[i]; ++i) 103    {104        int c=T[i]-‘a‘;105        while(j && !trie[j][c]) j=f[j];//一直找到可以匹配的字符节点 106        j=trie[j][c];107        if(val[j])//单词的最后一个字符108          countWords(j); 109        else if(last[j])//如果不是某个单词的最后一个节点 110          countWords(last[j]);111    }112 } 113 114 AC_Atomata ac;115 116 char T[1000005];117 char s[55];118 119 int main()120 {121     int t, n, i;122     scanf("%d", &t);123     while(t--)124     {125         ac.init();126         scanf("%d", &n);127         for(i=1; i<=n; ++i)128         {129             scanf("%s", s);130             ac.buildTrie(s);131     }132     scanf("%s", T);133     ac.getFail();134     ac.find(T);135     printf("%d\n", ac.cnt);136     }137     return 0;138 }