AC自动机50PTS求助
查看原帖
AC自动机50PTS求助
542698
封禁用户楼主2023/7/16 08:35
#include<bits/stdc++.h>
using namespace std;
int n,a[500005][65],cnt[500005],fail[500005],idx;
queue<int>q; 
int str_to_num(char x)
{
	if(x>='A'&&x<='Z')return x-'A';
    if(x>='a'&&x<='z')return x-'a'+26;
	return x-'0'+52;
}
void insert(string str)
{
	int temp=0;
	for(int i=0;i<str.size();i++)
	{
		int num=str_to_num(str[i]);
		if(!a[temp][num])a[temp][num]=++idx;
		temp=a[temp][num];
	}
	++cnt[temp];
}
void build()
{
	for(int i=0;i<26;i++)
		if(a[0][i])
		{
			fail[a[0][i]]=0;
			q.push(a[0][i]);
		}
	while(!q.empty())
	{
		int now=q.front();
		q.pop();
		for(int i=0;i<26;i++)
			if(a[now][i])
			{
				fail[a[now][i]]=a[fail[now]][i];
				q.push(a[now][i]);
			}
	}
}
int find(string str)
{
	int temp=0,now=0;
	for(int i=0;i<str.size();i++)
	{
		now=a[now][str_to_num(str[i])];
		for(int j=now;j!=0&&~cnt[j];j+=fail[j])
		{
			temp+=cnt[j];
			cnt[j]=-1;
		}
	}
	return temp;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		string s;
		cin>>s;
		insert(s);
	}
	build();
	string s;
	cin>>s;
	cout<<find(s);
}
2023/7/16 08:35
加载中...