代码

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e4+10,M=1e6+10,L=55;
int ch[N*L][26],cnt[N*L],idx;
int ne[N*L];//每个结点对应的next值 
int q[N*L];//队列 
char w[L],s[M];//w 单词 s 文章 
int T,n;
void init(){//清空 
	memset(ch,0,sizeof(ch));
	memset(cnt,0,sizeof(cnt));
	idx=0;
	memset(ne,0,sizeof(ne));
}
void insert(char w[]){//建树 
	int p=0;//从根开始 
	for(int i=0;w[i];i++){
		int x=w[i]-'a';
		if(!ch[p][x])ch[p][x]=++idx;
		p=ch[p][x];
	}
	cnt[p]++;//以当前结点结束的单词数加一 
}
//void bfs(){//求每个结点的next值 
//	int h=1,t=0;//默认为空
//	//将根节点下面的第一层结点入队  因为这一层结点next值都为0
//	for(int i=0;i<26;i++){
//		if(ch[0][i])q[++t]=ch[0][i];
//	}
//	//广搜计算每一层结点next值
//	while(h<=t){
//		int f=q[h];//上一层父结点编号 
//		for(int i=0;i<26;i++){
//			if(ch[f][i]){
//				int c=ch[f][i];//子结点编号 
//				int j=ne[f];//父结点next值
//				while(j&&!ch[j][i]){
//					j=ne[j];
//				}
//				if(ch[j][i]){
//					j=ch[j][i];
//				}
//				ne[c]=j;
//				q[++t]=c;//入队 
//			}
//		}
//		h++;//出队 
//	}
//}
void bfs(){
	int h=1,t=0;//默认为空
	//将根节点下面的第一层结点入队  因为这一层结点next值都为0
	for(int i=0;i<26;i++){
		if(ch[0][i])q[++t]=ch[0][i];
	}
	//广搜计算每一层结点next值
	while(h<=t){
		int f=q[h];//上一层父结点编号 
		for(int i=0;i<26;i++){
			if(ch[f][i]){
				int c=ch[f][i];//子结点编号 
				//父结点next值 
				ne[c]=ch[ne[f]][i];
				q[++t]=c;//入队 
			}
			else{
				//如果结点f不存在子结点i 存储假设存在结点i，其next值是多少 
				ch[f][i]=ch[ne[f]][i];
			}
		}
		h++;//出队 
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
//	scanf("%d",&T);
//	while(T--){
		init();
		scanf("%d",&n);
		while(n--){
			scanf("%s",w);
			insert(w);
		}//建树 
		bfs();//求每个结点的next值 
		scanf("%s",s);
		int res=0;
		for(int i=0,j=0;s[i];i++){//i 遍历s字符串   
								  //j 字典树从根开始遍历 
			int x=s[i]-'a';
			//匹配不上j回跳 
			while(j&&!ch[j][x])j=ne[j];
			if(ch[j][x])j=ch[j][x];//能匹配 j跳子结点 
			int p=j;
			while(p!=0){
				res+=cnt[p];
				cnt[p]=0;
				p=ne[p];//看以当前单词后缀为前缀单词是否存在 
			}
		}
		printf("%d\n",res);
//	}
	
	
	
	
	
	return 0;
}