AC自动机模版81pts求调
查看原帖
AC自动机模版81pts求调
755114
CD43楼主2025/7/26 22:20
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int n,m;
struct node{
	int next[55];
	int id;
	int who;
	int fail;
	int f;
	bool t;
}a[100001];
string xx[100001];
int tot;
int ctn(char x)
{
	if(x>='a'&&x<='z')return x-'a';
	return x-'A'+27;
}
int b[100001];
int build(int x,int deep,string y,int who)
{
//	cout<<y<<':'<<deep<<' '<<x<<' '<<who<<endl;
	if(deep==y.size())
	{
		a[x].who=who;
		a[x].t=1;
		return 0;
	}
	if(a[x].next[ctn(y[deep])])return build(a[x].next[ctn(y[deep])],deep+1,y,who);
	tot++;
	a[tot].id=ctn(y[deep]);
	a[x].next[ctn(y[deep])]=tot;
	a[tot].f=x;
	return build(a[x].next[ctn(y[deep])],deep+1,y,who);
}
int build_fail()
{
	queue<int>q;
	for(int i=0;i<=54;i++)
	{
		if(a[0].next[i])q.push(a[0].next[i]);
//		a[a[0].next[i]].fail=0;
	}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		
		int fail=a[a[u].f].fail;
		while(true)
		{
			if(a[u].f==0)break;
			if(a[fail].next[a[u].id]!=0)
			{
//				cout<<"OK"<<endl;
				a[u].fail=a[fail].next[a[u].id];
				break;
			}
			if(fail==0)break;
			fail=a[fail].fail;
		}
		
		for(int i=0;i<=54;i++)
		{
			if(a[u].next[i])q.push(a[u].next[i]);
		}
//		cout<<u<<':'<<a[u].fail<<endl;
	}
	return 0;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	while(cin>>n)
	{
		if(n==0)return 0;
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(xx,0,sizeof(xx));
		tot=0;
		string x;
		for(int i=1;i<=n;i++)
		{
			cin>>x;
			xx[i]=x;
			build(0,0,x,i);
		}
//		cout<<"build"<<endl;
		build_fail();
//		cout<<"build_fail"<<endl;
//		for(int i=0;i<=tot;i++)
//		{
//			cout<<i<<':'<<a[i].f<<' '<<a[i].fail<<' '<<(char)(a[i].id+'a')<<endl;
//		}
		int now=0;
		cin>>x;
		for(int i=0;i<x.size();i++)
		{
			if(a[now].next[ctn(x[i])])now=a[now].next[ctn(x[i])];
			else{
//				for(int j=0;j<55;j++)
//				{
//					if(a[i].next[j])cout<<(char)(a[a[i].next[j]].id+'a')<<' ';
//				}
//				cout<<endl;
				while(now!=0)
				{
					if(a[a[now].fail].next[ctn(x[i])])
					{
						now=a[a[now].fail].next[ctn(x[i])];
						break;
					}
					else now=a[now].fail;
//					cout<<now<<endl;
				}
			}
//			cout<<i<<' '<<now<<' '<<x[i]<<':'<<(char)(a[now].id+'a')<<endl;
			if(a[now].t)
			{
				b[a[now].who]++;
//				cout<<xx[a[now].who]<<endl;
			}
		}
//		cout<<"finish"<<endl;
		int ans=0;
		for(int i=1;i<=n;i++)ans=max(ans,b[i]);
		
		cout<<ans<<endl;
		for(int i=1;i<=n;i++)
		{
			if(b[i]==ans)cout<<xx[i]<<endl;
		}
	}
	return 0;
}

WA第一个和最后一个

2025/7/26 22:20
加载中...