社区讨论

64分求助

学术版参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lpnzpf2c
此快照首次捕获于
2023/12/02 19:48
2 年前
此快照最后确认于
2023/12/02 21:37
2 年前
查看原帖
RT,P3796
CPP
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int n,m,cnt,ans;
int sum[maxn],num[maxn],len;
char s[201][201],a[maxn];
struct edge{
	int idx,nxt[30];
}t[maxn*2];
inline int rd(){
	int x=0,f=1;char s=getchar();
	while(s<'0'||s>'9'){
		if(s=='-')f=-1;
		s=getchar();
	}
	while(s>='0'&&s<='9'){
		x=x*10+s-'0';
		s=getchar();
	}
	return x*f;
}
inline void build(int p,int i,int k){
	for(int i=1;i<=len;i++){
		int j=s[k][i]-'a';
		if(!t[p].nxt[j]){
			t[p].nxt[j]=++cnt;
		}
		p=t[p].nxt[j];
	}
	t[p].idx=k;
}
queue<int>q;
inline void insert(){
	for(int i=0;i<26;i++){
		if(t[0].nxt[i]){
			q.push(t[0].nxt[i]);
		}
	}		
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			int y=t[x].nxt[i];
			if(y!=0){
				sum[y]=t[sum[x]].nxt[i],q.push(y);
			}
			else{
				t[x].nxt[i]=t[sum[x]].nxt[i];
			}
		}
	}
	return;
}
inline void work(){
	int p;
	for(int i=1;i<=len;i++){
		p=t[p].nxt[a[i]-'a'];
		for(int j=p;j;j=sum[j]){
			num[t[j].idx]+=(t[j].idx!=0);
			ans=max(ans,num[t[j].idx]);
		}
	}
}
int main(){
	n=rd();
	while(n!=0){
		ans=0;
		for(int i=1;i<=n;i++){
			scanf("%s",s[i]+1);
			len=strlen(s[i]+1);
			build(0,1,i);
		}
		insert();
		scanf("%s",a+1);
		len=strlen(a+1);
		work();
		cout<<ans<<endl;
		for(int i=1;i<=n;i++){
			if(num[i]==ans){
				puts(s[i]+1);
			}
			num[i]=0;
			sum[i]=0;
		}
		for(int i=0;i<=cnt;i++){
			for(int j=0;j<26;j++){
				t[i].nxt[j]=0;
			}
			t[i].idx=0;
		}
		n=rd();
	}
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...