https://www.luogu.com.cn/problem/P3808

全T，1.20ms

#include<bits/stdc++.h>
using namespace std;
int n,cnt;
struct point{
	int son[30],fail;
	int final;
}trie[1000010];
void inser(char x[]){
	int len=strlen(x),pos=1,k;
	for(int i=0;i<len;i++){
		k=x[i]-'a';
		if(trie[pos].son[k]==0){
			trie[pos].son[k]=++cnt;
		} 
		pos=trie[pos].son[k];
	}
	trie[pos].final++;
}
queue<int>q;
int fail(int x){
	return trie[x].fail;
}
void bulid(){
	for(int i=0;i<26;i++){
		trie[0].son[i]=1;
	}
	trie[1].fail=0;
	q.push(1);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			int v=trie[u].son[i];
			if(v==0){
				trie[u].son[i]=trie[fail(u)].son[i];
			}
			else{
				trie[v].fail=trie[fail(u)].son[i];
				q.push(v);
			}
		}
	}
}
//wait for study under
int find(char x[]){
	int len=strlen(x),pos=1,ans=0,k;
	for(int i=0;i<len;i++){
		k=trie[pos].son[(int)(x[i]-'a')];
		while(k!=0 && trie[k].final!=-1){
			ans+=trie[k].final;
			trie[k].final=-1;
			k=fail(k);
		}
		pos=trie[pos].son[(int)(x[i]-'a')];
	}
	return ans;
}
//
int main(){
	scanf("%d",&n);
	char x[1000010];
	for(int i=1;i<=n;i++){
		scanf("%s",x);
		inser(x);
	}
	bulid();
	scanf("%s",x);
	printf("%d",find(x));
	return 0;
}