简单的数据都能过,就是找不到问题在哪,求大佬施救orz
#include<bits/stdc++.h>
using namespace std;
int n,cnt;
string a;
queue<int> q;
struct A{
int son[26],f,fail;
}t[1000010];
void insert(string s)
{
int l=s.length(),u=1;
for(int i=0;i<l;i++)
{
int v=s[i]-'a';
if(!t[u].son[v])
{
cnt++;
t[u].son[v]=cnt;
}
u=cnt;
}
t[u].f++;
}
void getfail()
{
for(int i=0;i<26;i++)
t[0].son[i]=1;
q.push(1);
t[1].fail=0;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=0;i<26;i++)
{
int v=t[u].son[i];
int Fail=t[u].fail;
if(!v)
{
t[u].son[i]=t[Fail].son[i];
continue;
}
t[v].fail=t[Fail].son[i];
q.push(v);
}
}
}
int query(string s)
{
int u=1,ans=0,l=s.length();
for(int i=0;i<l;i++)
{
int v=s[i]-'a';
int k=t[u].son[v];
while(k>1&&t[k].f!=-1)
{
ans+=t[k].f;
t[k].f=-1;
k=t[k].fail;
}
u=t[u].son[v];
}
return ans;
}
int main()
{
cnt=1;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>a;
insert(a);
}
getfail();
cin>>a;
printf("%d",query(a));
return 0;
}