以前写的太搓了,照着白书改了改。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; int ch[555555][26],val[555555]; int f[555555],last[555555]; int sz,n; char str[55]; char str2[1000009]; void init() { sz=0; memset(ch[0],0,sizeof(ch[0])); } void insert(char *a) { int u=0,l=strlen(a); for(int i=0;i<l;i++) { int c=a[i]-'a'; if(!ch[u][c]) { ch[u][c]=++sz; memset(ch[sz],0,sizeof(ch[sz])); val[sz]=0; } u=ch[u][c]; } val[u]++; } void getfail() { queue<int>q; f[0]=0; for(int i=0;i<26;i++) { int u=ch[0][i]; if(u) { f[u]=0; q.push(u); last[u]=0; } } while(!q.empty()) { int r=q.front(); q.pop(); for(int i=0;i<26;i++) { int u=ch[r][i]; if(!u)continue; q.push(u); int v=f[r]; while(v&&!ch[v][i])v=f[v]; f[u]=ch[v][i]; last[u]=val[f[u]]?f[u]:last[f[u]]; } } } int query(char *a) { int ans=0,l=strlen(a); int u=0; for(int i=0;i<l;i++) { int c=a[i]-'a'; while(u&&!ch[u][c])u=f[u]; if(ch[u][c])u=ch[u][c]; else u=0; int temp=u; while(temp&&val[temp]!=-1) { ans+=val[temp]; val[temp]=-1; temp=last[temp]; } } return ans; } int main() { int t; scanf("%d",&t); while(t--) { init(); scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%s",str); insert(str); } getfail(); scanf("%s",str2); printf("%d\n",query(str2)); } return 0; }