社区讨论
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 条回复,欢迎继续交流。
正在加载回复...