答案好像少了一百多个吧
调吐了
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e6+5;
int trie[maxn][26],cnt=1;
int have[maxn];
void insert(string k)
{
int n=k.size(),p=1;
for(int i=0;i<n;i++)
{
int c=k[i]-'a';
if(!trie[p][c]) trie[p][c]=++cnt;
p=trie[p][c];
}
have[p]++;
}
int fa[maxn],fail[maxn];
int val[maxn];
queue <pair<int,int> > q;
void dfs(int u)
{
for(int i=0;i<26;i++)
{
if(trie[u][i])
{
val[trie[u][i]]=i;
fa[trie[u][i]]=u;
dfs(trie[u][i]);
}
}
}
void bfs()
{
q.push(make_pair(1,0));
fail[1]=1;
while(!q.empty())
{
int u=q.front().first,ceng=q.front().second;
q.pop();
for(int i=0;i<26;i++) if(trie[u][i]) q.push(make_pair(trie[u][i],ceng+1));
if(ceng==1) fail[u]=1;
if(ceng>1)
{
int p=fail[fa[u]];
while(p>1&&!trie[p][val[u]]) p=fail[fa[p]];
if(trie[p][val[u]]) fail[u]=trie[p][val[u]];
else fail[u]=1;
}
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
string k;
cin>>k;
insert(k);
}
fa[1]=0;
dfs(1);
bfs();
string s;
cin>>s;
int ssize=s.size();
int u=1,ans=0;
for(int i=0;i<ssize;i++)
{
if(have[u])
{
ans+=have[u];
have[u]=0;
}
int c=s[i]-'a';
if(trie[u][c])
{
u=trie[u][c];
}
else
{
while(u>1&&!trie[u][c])
{
u=fail[u];
if(have[u])
{
ans+=have[u];
have[u]=0;
}
}
if(have[u])
{
ans+=have[u];
have[u]=0;
}
if(trie[u][c]) u=trie[u][c];
if(have[u])
{
ans+=have[u];
have[u]=0;
}
}
if(have[u])
{
ans+=have[u];
have[u]=0;
}
}
printf("%d",ans);
return 0;
}