第二个数据wa求助
查看原帖
第二个数据wa求助
107266
starco楼主2022/2/21 21:14

简单的数据都能过,就是找不到问题在哪,求大佬施救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;
}
2022/2/21 21:14
加载中...