纯粹的模版。。。
学习模版总会是一个快乐的过程。。。。
#include <cstdio>
#include <cstdlib>
#include <string>
#include <climits>
#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <sstream>
#include <map>
#include <cstring>
#include <queue>
using namespace std;
const int MAX_NODE = 55*10000;//MAX_NODE = StringNumber * StringLength
const int CHILD_NUM = 26;//节点个数,一般字符形式的题26个
const int mod = 20090717;//特定题目需要
struct ACAutomaton {int chd[MAX_NODE][CHILD_NUM];//每个节点的儿子,即当前节点的状态转移int val[MAX_NODE];//记录题目给的关键数据int fail[MAX_NODE];//传说中的fail指针int Q[MAX_NODE];//队列,用于广度优先计算fail指针int ID[128];//字母对应的IDint sz;//已使用节点个数//int dp[2][MAX_NODE][1<<10];//特定题目需要void init() {fail[0] = 0;for (int i = 0 ; i < CHILD_NUM ; i ++) {ID[i+'a'] = i;}}//重新建树需先Resetvoid Reset() {memset(chd[0] , 0 , sizeof(chd[0]));memset(val,0,sizeof(val));sz = 1;}//将权值为key的字符串a插入到trie中void insert(char *a,int key) {int p = 0;int len=strlen(a);for (int i=0;i<len;i++) {int c = ID[a[i]];if (!chd[p][c]) {memset(chd[sz] , 0 , sizeof(chd[sz]));val[sz] = 0;chd[p][c] = sz ++;}p = chd[p][c];}val[p] += key;}void build_ac() {int *s = Q , *e = Q;for (int i = 0 ; i < CHILD_NUM ; i ++) {if (chd[0][i]) {fail[ chd[0][i] ] = 0;*e ++ = chd[0][i];}}while (s != e) {int u = *s++;for (int i = 0 ; i < CHILD_NUM ; i ++) {int &v = chd[u][i];if (v) {*e ++ = v;fail[v] = chd[ fail[u] ][i];//以下一行代码要根据题目所给val的含义来写// val[v] += val[ fail[v] ];} else {v = chd[ fail[u] ][i];}}}}//解题,特定题目需要int Work(char str[]) {int len=strlen(str);int ans,i,root,tp,key;ans=root=0;for(i=0;i<len;i++){tp=ID[str[i]];root=chd[root][tp];key=root;while(key!=0&&val[key]!=0){ans+=val[key];val[key]=0;key=fail[key];}}return ans;}
}AC;
char str[1100000];
int main() {int n ,T;AC.init();scanf("%d",&T);while(T--) {AC.Reset();scanf("%d",&n);for (int i = 0 ; i < n ; i ++) {char temp[55];scanf("%s",temp);AC.insert(temp , 1);}AC.build_ac();scanf("%s",str);printf("%d\n",AC.Work(str));}return 0;
}