第一次打

第三个样例没过，大概匹配部分出问题了

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int trie[maxn][30],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];
		}
		
	}
	printf("%d",ans);
	
	
	return 0;
}