#include <cstdio>#include <cstring>#include <cmath>#include <queue>#include <algorithm>#define MAXN 500000+10using namespace std;char str[1000000+10];struct Trie{int next[MAXN][30], fail[MAXN], word[MAXN];int root, L;int newnode()//新建节点{for(int i = 0; i < 26; i++)next[L][i] = -1;//初始化-1word[L++] = 0;return L-1;}void init()//初始化节点{L = 0;root = newnode();}//插入字符串 同字典树 比较好理解void Insert(char *buf){int len = strlen(buf);int now = root;for(int i = 0; i < len; i++){if(next[now][buf[i]-'a'] == -1)next[now][buf[i]-'a'] = newnode();//新建now = next[now][buf[i]-'a'];}word[now]++;//数目加一}//构造失败指针void Build(){queue<int> Q;fail[root] = root;for(int i = 0; i < 26; i++){if(next[root][i] == -1)next[root][i] = root;//指向rootelse{fail[next[root][i]] = root;Q.push(next[root][i]);}}while(!Q.empty()){int now = Q.front();Q.pop();for(int i = 0; i < 26; i++){if(next[now][i] == -1)next[now][i] = next[fail[now]][i];else{fail[next[now][i]]=next[fail[now]][i];Q.push(next[now][i]);}}}}//查询 类似KMPint Query(char *buf){int len = strlen(buf);int now = root;int ans = 0;//查询结果for(int i = 0; i < len; i++){now = next[now][buf[i]-'a'];int temp = now;//记录now 从当前开始匹配while(temp != root)//直到指向root 为止{ans += word[temp];word[temp] = 0;temp = fail[temp];}}return ans;}};Trie ac;int main(){int t, N;scanf("%d", &t);while(t–){scanf("%d", &N);ac.init();for(int i = 0; i < N; i++){scanf("%s", str);ac.Insert(str);}ac.Build();scanf("%s", str);printf("%d\n", ac.Query(str));}return 0;}
，巨龟千岁，却也平淡无奇;昙花瞬间，却能绚丽无比。
