我太菜了
棒神%%%
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstdlib> 5 #include<cstring> 6 #include<algorithm> 7 #include<vector> 8 #include<queue> 9 #define inf 2139062143 10 #define ll long long 11 #define MAXN 1010101 12 using namespace std; 13 inline int read() 14 { 15 int x=0,f=1;char ch=getchar(); 16 while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} 17 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} 18 return x*f; 19 } 20 char ch[MAXN],str[MAXN]; 21 int tr[MAXN][28],n,s[MAXN],fail[MAXN],ans,sz; 22 void insert() 23 { 24 int len=strlen(ch),pos=0,k; 25 for(int i=0;i<len;i++) 26 { 27 int k=ch[i]-'a'; 28 if(!tr[pos][k]) tr[pos][k]=++sz; 29 pos=tr[pos][k]; 30 } 31 s[pos]++; 32 } 33 void build() 34 { 35 queue <int> q; 36 for(int i=0;i<26;i++) if(tr[0][i]) {fail[tr[0][i]]=0;q.push(tr[0][i]);} 37 while(!q.empty()) 38 { 39 int k=q.front();q.pop(); 40 for(int i=0;i<26;i++) 41 if(tr[k][i]) fail[tr[k][i]]=tr[fail[k]][i],q.push(tr[k][i]); 42 else tr[k][i]=tr[fail[k]][i]; 43 } 44 } 45 void query() 46 { 47 int len=strlen(str),pos=0,k; 48 for(int i=0;i<len;i++) 49 { 50 k=str[i]-'a'; 51 pos=tr[pos][k]; 52 for(int j=pos;j&&~s[j];j=fail[j]) ans+=s[j],s[j]=-1; 53 } 54 } 55 int main() 56 { 57 n=read(); 58 while(n--) {scanf("%s",ch);insert();} 59 build(); 60 scanf("%s",str); 61 query();printf("%d",ans); 62 }