求助RE
查看原帖
求助RE
25891
沧桑の天骄楼主2022/3/16 14:31

下载样例后本地可以运行,评测却一直RE

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ll long long
using namespace std;
inline ll read(){
	ll x=0,w=1;
	char aa=getchar();
	while(aa<'0'||aa>'9'){
		if(aa=='-'){
			w=-1;
		}
		aa=getchar();
	}
	while(aa>='0'&&aa<='9'){
		x=(x<<3)+(x<<1)+aa-'0';
		aa=getchar();
	}
	return x*w;
}
const int N=1e6+10;

int n,tot;
string s,t[N];
int ch[N][31],fail[N],num[N];
queue<int> q;
struct node{
	int num,sum;
}ans[N];

void cle(int x){
	memset(ch[x],0,sizeof(ch[x]));
	fail[x]=0,num[x]=0;
}

void insert(string t,int id){
	int u=0,le=t.size();
	for(int i=0;i<le;i++){
		int now=t[i]-'a';
		if(!ch[u][now]){
			ch[u][now]=++tot;
			cle(tot);
		}
		u=ch[u][now];
	}
	num[u]=id;
}

void getfail(){
	for(int i=0;i<26;i++){
		int c=ch[0][i];
		if(c){
			fail[c]=0;
			q.push(c);
		}
	}
	while(!q.empty()){
		int u=q.front(),f=fail[u];
		q.pop();
		for(int i=0;i<26;i++){
			int c=ch[u][i];
			if(c){
				fail[c]=ch[f][i];
				q.push(c);
			}
			else ch[u][i]=ch[f][i];
		}
	}
}

int getans(string s){
	int u=0,len=s.size();
	for(int i=0;i<len;i++){
		int now=s[i]-'a';
		u=ch[u][now];
		for(int v=u;v;v=fail[v]){
			ans[num[v]].sum++;
		}
	}
}

bool cmp(node a,node b){
	return a.sum==b.sum?a.num<b.num:a.sum<b.sum;
}

int main(){
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
    while(1){
	    n=read();
	    if(n==0) break;
	    tot=0;
	    cle(0);
	    for(int i=1;i<=n;i++){
		    cin>>t[i];
	    	ans[i].num=i,ans[i].sum=0;
		    insert(t[i],i);
	    }
	    getfail();
	    cin>>s;
	    getans(s);
	    sort(ans+1,ans+n+1,cmp);
	    printf("%d\n",ans[1].sum);
	    cout<<t[ans[1].num]<<endl;
	    for(int i=2;i<=n;i++){
	    	if(ans[i].sum==ans[i-1].sum) cout<<t[ans[i].num]<<endl;
	    	else break;
	    }
    }
    return 0;
}
2022/3/16 14:31
加载中...