AC,但是提问
查看原帖
AC,但是提问
775469
danzhu2022楼主2024/6/30 17:41
#include<bits/stdc++.h>
using namespace std;
const int Nm=1e6+3;
struct node{
	int fail;
	int f;
	int end;
	int vis[30];
}a[Nm];
map<int,string>ma;
map<string,int>mb;  
int sum[Nm];
int cnt=0;
void build(string s)
{
	int l=s.size();
	int now=0;
	for(int i=0;i<l;i++)
	{
		if(a[now].vis[s[i]-'a']==0)
		{
			a[now].vis[s[i]-'a']=++cnt;
		}
		now=a[now].vis[s[i]-'a'];
	}
	a[now].end++;
	a[now].f=mb[s];
}
void getfail(){
	int now=0;
	queue<int>AA;
	a[0].fail=0;
	for(int i=0;i<26;i++)
	{
		if(a[now].vis[i]!=0)
		{
			a[a[now].vis[i]].fail=0;
			AA.push(a[now].vis[i]);
		}
	}
	while(!AA.empty())
	{
		now=AA.front();
		AA.pop();
		for(int i=0;i<26;i++)
		{
			if(a[now].vis[i]!=0)
			{
				a[a[now].vis[i]].fail=a[a[now].fail].vis[i];
				AA.push(a[now].vis[i]);	
			}
			else
				a[now].vis[i]=a[a[now].fail].vis[i];
		}
	}
}
int check(string s){
	int ans=0;
	int l=s.size();
	int now=0;
	for(int i=0;i<l;i++)
	{
		now=a[now].vis[s[i]-'a'];
		for(int t=now;t!=0&&a[t].end!=-1;t=a[t].fail)
		{
			if(a[t].end!=0)
			{
				sum[a[t].f]++;
				ans=max(ans,sum[a[t].f]);
				
			//	a[t].end=-1;
			}
		}
	}
	return ans;
}
int main(){
	string s;
	int n;
	while(cin>>n)
	{
		if(n==0)break;
		ma.clear();
		mb.clear();
		for(int i=0;i<=n*70;i++)
		{
			sum[i]=0;
			a[i].end=0;
			a[i].f=0;
			a[i].fail=0;
			for(int j=0;j<30;j++)a[i].vis[j]=0;
		}
		for(int i=1;i<=n;i++)
		{
			cin>>s;
			if(mb[s]==0)
			{
				mb[s]=i;
				ma[i]=s;
			}
			build(s);
		}
		getfail();
		cin>>s;
		int res=check(s);
		cout<<res<<endl;
		for(int i=1;i<=n;i++)
		{
			if(sum[i]==res)cout<<ma[i]<<endl;
		
		}
	}
}

check函数里面为什么注释掉那一行就对了啊

2024/6/30 17:41
加载中...