样例也过不了,机房里的同学每一个会的
#include<bits/stdc++.h>
using namespace std;
int n,ans;
string s;
int wei(char a){return (int)(a-'a');}
struct trie{
trie *next[26],*fail;
int bj;
};
trie *root,*superRoot;
void csh(trie *u){
u->bj=0;u->fail=NULL;
for(int i=0;i<26;i++) u->next[i]=NULL;
}
void init(){
root->fail=superRoot;
for(int i=0;i<26;i++){
superRoot->next[i]=root;
}
superRoot->bj=-1;
}
void build(string s){
trie *ls,*place;
place=root;
for(int i=0;i<s.size();i++){
int u=wei(s[i]);
if(place->next[u]==NULL){
ls=new trie;
csh(ls);
place->next[i]=ls;
}else ls=place->next[u];
place=ls;
}
place->bj++;
}
void build_ac(){
queue<trie*>q;
q.push(root);
while(!q.empty()){
trie *ls;
ls=q.front();
q.pop();
for(int i=0;i<26;i++){
if(ls->next[i]==NULL){
ls->next[i]=ls->fail->next[i];
}else{
ls->next[i]->fail=ls->fail->next[i];
q.push(ls->next[i]);
}
}
}
}
void find(string s){
trie *place=superRoot->next[0];
for(int j=0;j<s.size();j++){
int i=wei(s[j]);
place=place->next[i];
for(trie *ls=place;ls->bj!=-1;ls=ls->fail){
ans+=ls->bj;
ls->bj=-1;
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
root=new trie;csh(root);
superRoot=new trie;csh(superRoot);
init();
for(int i=1;i<=n;i++){
cin>>s;
build(s);
}
build_ac();
cin>>s;root=superRoot->next[0];
find(s);
printf("%d",ans);
}
/*
3
chenkuo
chenpingye
laojiang
chenkuochenkuolaojiangchenlaojiangchenpingyelaojiang
*/