求助AC自动机
查看原帖
求助AC自动机
92682
Eric_cai楼主2021/7/28 10:20
#include<iostream>
#include<cstdio>
#include<queue>
#define maxn 2000005
using namespace std;
string s[maxn],t;
int fail[maxn],son[maxn][30],ed[maxn],cnt,ans,n;
void ins(int id)
{
	int now=0;
	for(int i=0;i<s[id].size();i++)
	{
		if(son[now][s[id][i]-'a'+1]!=0) now=son[now][s[id][i]-'a'+1];
		else now=son[now][s[id][i]-'a'+1]=++cnt;
	}
	ed[now]++;
}
void get_fail()
{
	queue<int> q;
	q.push(0);
	while(!q.empty())
	{
		int fr=q.front();
		q.pop();
		for(int i=1;i<=26;i++)
		{
			if(fr!=0) fail[son[fr][i]]=son[fail[fr]][i];
			if(son[fr][i]!=0) q.push(son[fr][i]);
		}
	}
}
void get_ans()
{
	int now=0,x;
	for(int i=0;i<t.size();i++)
	{
		now=son[now][t[i]-'a'+1];
		x=now;
		while(x!=0 && ed[x]!=-1)
		{
			ans+=ed[x];
			ed[x]=-1;
			x=fail[x];
		}
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
	    cin>>s[i];
	    ins(i);
	}
	get_fail();
	cin>>t;
	get_ans();
	printf("%d\n",ans);
	return 0;
}
2021/7/28 10:20
加载中...