#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int n,last[200005],f[200005],tr[200005][30],v[200005],sum[200005],maxn,tot,ans[200005],flag[200005],in[200005];
char st1[200005],st2[1000005];
void insert(char* st,int va)
{
int len=strlen(st),p=0;
for(int i=0;i<len;i++)
{
int ch=st[i]-'a'+1;
if(!tr[p][ch])
{
memset(tr[++tot],0,sizeof(tr[tot]));
tr[p][ch]=tot;
}
p=tr[p][ch];
}
flag[va]=p;
}
void getpre()
{
queue<int> q;
for(int i=1;i<=26;i++)
if(tr[0][i]) q.push(tr[0][i]);
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=1;i<=26;i++)
{
if(!tr[x][i])
{
tr[x][i]=tr[f[x]][i];
continue;
}
f[tr[x][i]]=tr[f[x]][i];
in[f[tr[x][i]]]++;
q.push(tr[x][i]);
}
}
}
void find(char* st)
{
int len=strlen(st),p=0;
for(int i=0;i<len;i++)
{
int ch=st[i]-'a'+1;
p=tr[p][ch];
ans[p]++;
}
}
void topu()
{
queue<int> q;
for(int i=1;i<=tot;i++)
if(!in[i]) q.push(i);
while(q.size())
{
int x=q.front();
q.pop();
int u=f[x];
ans[u]+=ans[x];
if(!(--in[u])) q.push(u);
}
}
int main()
{
scanf("%d",&n);
if(n==0)return 0;
for(int i=1;i<=n;i++)
{
scanf("%s",st1);
insert(st1,i);
}
getpre();
scanf("%s",st2);
find(st2);
topu();
for(int i=1;i<=n;i++)
printf("%d\n",ans[flag[i]]);
return 0;
}
为什么我把vis数组注释掉就不对了,我其他地方完全没有用过vis数组??
我把vis数组写上,就AC了