求助,本地AC,你谷MLE!
查看原帖
求助,本地AC,你谷MLE!
721959
封禁用户楼主2023/1/28 20:39

代码:

#include<bits/stdc++.h>
using namespace std;
int n,ne[26000005],c[1000005][30],cnt,en[26000005];
char s[153][75],w[1000006];
struct abab{
	int ans,num;//ans数量,num标记
}a[153];
bool cmp(abab f1,abab f2){
	if(f1.ans!=f2.ans)return f1.ans>f2.ans;
	return f1.num<f2.num;
}
inline int read(){
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x;
}
void join(int pp){
	scanf("%s",s[pp]);
	int u=1,l=strlen(s[pp]);
	for(int i=0;i<l;++i){
		int p=s[pp][i]-96;
		if(!c[u][p])c[u][p]=++cnt;
		u=c[u][p];
	}
	en[u]=pp;
//	cout<<u<<'\n';
}
void bfs(){
	queue<int>q;q.push(1);
	for(int i=1;i<27;i++)c[0][i]=1;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=1;i<=26;++i){
			if(!c[u][i])c[u][i]=c[ne[u]][i];
			else{
				ne[c[u][i]]=c[ne[u]][i];
				q.push(c[u][i]);
			}
		}
	}
}
void find(){
	scanf("%s",w);
	int u=1,b,l=strlen(w),d;
	for(int i=0;i<l;++i){
		u=c[u][w[i]-96];
		for(int j=u;j;j=ne[j]){
			a[en[j]].ans++;
		}
	}
}
int main(){
	while(1){
		n=read();
		if(n==0)return 0;cnt=1;memset(c,0,sizeof c);
		memset(ne,0,sizeof ne);memset(en,0,sizeof en);
		for(int i=1;i<=n;i++)join(i),a[i].num=i,a[i].ans=0;
		bfs();
		find();
		sort(a+1,a+n+1,cmp);
		cout<<a[1].ans<<'\n'<<s[a[1].num]<<'\n';
		for(int i=2;i<=n;++i){
			if(a[i].ans==a[i-1].ans)cout<<s[a[i].num]<<'\n';
			else break;
		}
	}
} 
2023/1/28 20:39
加载中...