这题号也是醉了，（对AC无情的嘲讽）
AC自动机的裸题？？？不知道。。。。不会，，感觉现在心态已经boom！！！！！！！！
搞出trie树，搞出fail数组，然后搞一搞就行了
1 #include<bits/stdc++.h> 2 #define N 1000005 3 #define LL long long 4 #define inf 0x3f3f3f3f 5 using namespace std; 6 inline int ra() 7 { 8 int x=0,f=1; char ch=getchar(); 9 while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();} 10 while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} 11 return x*f; 12 } 13 char s[51],m[1000001]; 14 int T,n,sz,ans; 15 int a[500001][27],q[500001],point[500001],danger[500001]; 16 bool mark[500001]; 17 18 void ins() //trie 19 { 20 int now=1,l=strlen(s); 21 for (int i=0; i<l; i++) 22 { 23 int t=s[i]-'a'+1; 24 if (a[now][t]) now=a[now][t]; 25 else now=a[now][t]=++sz; 26 } 27 danger[now]++; 28 } 29 void ACmatch() //fail 30 { 31 int t=0,w=1,now; 32 q[0]=1; point[1]=0; 33 while (t<w) 34 { 35 now=q[t++]; 36 for (int i=1; i<=26; i++) 37 { 38 if (!a[now][i]) continue; 39 int k=point[now]; 40 while (!a[k][i]) k=point[k]; 41 point[a[now][i]]=a[k][i]; 42 q[w++]=a[now][i]; 43 } 44 } 45 } 46 void solve() 47 { 48 int k=1,l=strlen(m); 49 for (int i=0; i<l; i++) 50 { 51 mark[k]=1; 52 int t=m[i]-'a'+1; 53 while (!a[k][t]) k=point[k]; 54 k=a[k][t]; 55 if (!mark[k]) 56 for (int j=k;j;j=point[j]) 57 { 58 ans+=danger[j]; 59 danger[j]=0; 60 } 61 } 62 printf("%d ",ans); 63 } 64 int main() 65 { 66 int T=ra(); 67 while (T--) 68 { 69 sz=1; ans=0; n=ra(); 70 for (int i=1; i<=26; i++) a[0][i]=1; 71 while (n--) 72 { 73 scanf("%s",s); 74 ins(); 75 } 76 ACmatch(); scanf("%s",m); solve(); 77 for (int i=1; i<=sz; i++) 78 { 79 point[i]=danger[i]=mark[i]=0; 80 for (int j=1; j<=26; j++) 81 a[i][j]=0; 82 } 83 } 84 return 0; 85 }