求助,全RE
查看原帖
求助,全RE
229957
Wu_while楼主2021/6/22 20:28
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define MAXN 10000010
using namespace std;
struct trie
{
	int ch[26];
	int fail,num;
}
a[MAXN];
int n,tot=1,ans;
char s[1000010];
queue<int> q;
int add_string()
{
	int t=1;
	for(int i=0;i<strlen(s);i++)
	{
		int v=s[i]-'a';
		if(!a[t].ch[v])
			a[t].ch[v]=++tot;
		t=a[t].ch[v];
	}
	a[t].num++;
}
void get_fail()
{
	for(int i=0;i<26;i++)
		a[0].ch[i]=1;
	q.push(1);
	a[1].fail=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<26;i++)
		{
			int v=a[u].ch[i];
			int Fail=a[u].fail;
			if(!v)
			{
				a[u].ch[i]=a[Fail].ch[i];
				continue;
			}
			a[v].fail=a[Fail].ch[i];
			q.push(v);
		}
	}
}
void check()
{
	int t=1;
	for(int i=0;i<strlen(s);i++)
	{
		int v=s[i]-'a';
		int k=a[t].ch[v];
		while(k>1&&a[k].num!=-1)
		{
			ans+=a[k].num;
			a[k].num=-1;
			k=a[k].fail;
		}
		t=a[t].ch[v];
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s);
		add_string();
	}
	get_fail();
	scanf("%s",s);
	check();
	printf("%d",ans);
	return 0;
 } 
2021/6/22 20:28
加载中...