求助:一直RE+MLE
查看原帖
求助:一直RE+MLE
593595
_Aurore_楼主2023/1/10 08:47
#include<bits/stdc++.h>
#define MAXN 100001
#define int long long
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-f;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
} 
int n,back[MAXN],tot[MAXN];
int trie[MAXN][26],cnt;
struct node{
	int num,fail;
}t[MAXN];
string s[MAXN],s2;
void insert(string s,int len,int que){
	int rot=0;
	for(int i=0;i<len;i++){
		int c=s[i]-'a';
		if(!trie[rot][c])
			trie[rot][c]=++cnt;
		rot=trie[rot][c];
	}
	t[rot].num++;
	back[que]=rot;
}
queue<int> q;
void Fail(){
	for(int i=0;i<26;i++)
		if(trie[0][i])
			q.push(trie[0][i]);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			int v=trie[u][i];
			if(v){
				t[v].fail=trie[t[u].fail][i];
				q.push(v);
			}
			else
				trie[u][i]=trie[t[u].fail][i];
		}
	}
}
vector<int> e[MAXN];
void dfs(int x,int dad){
	for(int i=0;i<e[x].size();i++){
		int to=e[x][i];
		if(to!=dad){
			dfs(to,x);
			tot[x]+=tot[to]; 
		}
	}
}
signed main(){
	n=read();
	while(n){
		memset(back,0,sizeof(back));
		memset(trie,0,sizeof(trie));
		memset(t,0,sizeof(t));
		memset(tot,0,sizeof(tot));
		for(int i=1;i<MAXN;i++)
			e[i].erase(e[i].begin(),e[i].end());
		for(int i=1;i<=n;i++){
			cin>>s[i];
			insert(s[i],s[i].length(),i);
		}
		Fail();
		cin>>s2;
		int rot=0;
		for(int i=0;i<s2.length();i++){
			rot=trie[rot][s2[i]-'a'];
			++tot[rot];
		}
		for(int i=1;i<=cnt;i++){
			e[i].push_back(t[i].fail);
			e[t[i].fail].push_back(i);
		}
		dfs(0,MAXN);
		int ans=0;
		for(int i=1;i<=n;i++)
			ans=max(ans,tot[back[i]]);
		cout<<ans<<endl;
		for(int i=1;i<=n;i++)
			if(tot[back[i]]==ans)
				cout<<s[i]<<endl;
		n=read();	
	}
	return 0;
} 
2023/1/10 08:47
加载中...