1 // File Name: temp.cpp  2 // Author: darkdream  3 // Created Time: 2014年09月11日 星期四 15时18分26秒  4   5 #include<vector>  6 #include<list>  7 #include<map>  8 #include<set>  9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #include<queue> 25 #define LL long long 26 #define maxn 500010 27 using namespace std; 28 struct Trie 29 { 30    int next[maxn][26],fail[maxn],end[maxn]; 31    int root, L; 32    int newnode() 33    { 34        for(int i = 0 ;i < 26;i ++) 35           next[L][i] = -1; 36        end[L++] = 0 ; 37        return L-1; 38    } 39    int init() 40    { 41       int L = 0 ;  42       root = newnode(); 43    } 44    int insert(char buf[]) 45    { 46       int len = strlen(buf); 47       int now = root; 48       for(int i = 0 ;i < len ;i ++) 49       { 50          if(next[now][buf[i] - ‘a‘] ==  -1) 51          { 52              next[now][buf[i] - ‘a‘] = newnode(); 53          } 54          now = next[now][buf[i]-‘a‘]; 55       } 56       end[now]++; 57    } 58    void build() 59    { 60        queue<int> Q;  61        //这里为何要用优先队列来解决这个问题，主要原因是fail指针是按层数来的。 62        fail[root] = root;  63        for(int i = 0;i < 26;i ++) 64        { 65             if(next[root][i] == -1) 66             { 67                next[root][i] = root;  //指向root 是没有问题的，我们主要是通过end 数组对个数进行计数的。     68             }else{ 69                fail[next[root][i]] = root; 70                Q.push(next[root][i]); 71             } 72        } 73        while(!Q.empty()) 74        { 75           int now = Q.front(); 76           Q.pop(); 77           for(int i = 0 ;i < 26;i ++) 78           { 79              if(next[now][i] == -1) 80                  next[now][i] =  next[fail[now]][i];  81              else{ 82                 fail[next[now][i]] = next[fail[now]][i]; 83                 Q.push(next[now][i]); 84              } 85           } 86        } 87    } 88    int query(char buf[]) 89    { 90       int len = strlen(buf); 91       int now = root ;  92       int res = 0 ;  93       for(int i = 0 ;i < len;i ++) 94       { 95         now = next[now][buf[i] -‘a‘]; 96         int temp = now ;  97         while(temp != root) 98         { 99            res += end[temp];100            end[temp] = 0 ; 101            temp = fail[temp];//  不断的寻找 fail 指针 因为会出线这样的字符串  abcd bcd cd102         }103       }104       return res;105    }106 };107 char buf[1000010];108 Trie ac;109 int main(){110     int T;111     int n;112     scanf("%d",&T);113     {114       while(T--)115       {116          scanf("%d",&n);117          ac.init();118          for(int i = 0 ;i < n;i ++)119          {120             scanf("%s",buf);121             ac.insert(buf);122          }123          ac.build();124          scanf("%s",buf);125          printf("%d\n",ac.query(buf));126       }127     }128 return 0;129 }