萌新刚学ACAM 0.01ms,样例不过球调
查看原帖
萌新刚学ACAM 0.01ms,样例不过球调
286448
Eason2009楼主2022/6/30 16:17
#include<bits/stdc++.h>
#define maxn 1000005
using namespace std;
int ch[maxn][30],tot,n,fail[maxn],end[maxn];
char s[maxn],t[maxn];
queue<int>q;
void ins(char s[])
{
	int len=strlen(s+1),now=0;
	for(int i=1;i<=len;i++)
	{
		if(!ch[now][s[i]-'a']) ch[now][s[i]-'a']=++tot;
		now=ch[now][s[i]-'a'];
	}
	end[now]++;
	return;
}
void AC()
{
	for(int i=0;i<26;i++)
	{
		if(ch[0][i]) q.push(ch[0][i]);
	}
	while(!q.empty())
	{
		int now=q.front();
		q.pop();
		for(int i=0;i<26;i++)
		{
			if(ch[now][i])
			{
				fail[ch[now][i]]=ch[fail[now]][i];
				q.push(ch[now][i]);	
			}
			else ch[now][i]=ch[fail[now]][i];
		}
	}
	return;
}
int query()
{
	int len=strlen(t+1),now=0,ans=0;
	for(int i=1;i<=len;i++)
	{
		now=ch[now][t[i]-'a'];
		int v=now;
		while(v&&end[v]!=-1)
		{
			ans+=end[v];
			end[v]=-1;
			v=fail[v];
		}
	}
	return ans;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s+1;
		ins(s+1);
	}
	AC();
	cin>>t+1;
	cout<<query();
	return 0;
}

2022/6/30 16:17
加载中...