社区讨论
蒟蒻刚写helloworld,wa求助
P3796AC 自动机(简单版 II)参与者 5已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @mi7di5ld
- 此快照首次捕获于
- 2025/11/20 19:53 4 个月前
- 此快照最后确认于
- 2025/11/20 19:53 4 个月前
CPP
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int n;const int maxn=155,maxm=155*75;
string ss[maxn];string tt;
int tre[maxm][27];int din;
int bac[maxm];
int val[maxm];
int ans[maxn];
int main(){
while(scanf("%d",&n)==1){
if(n==0)break;
rep(i,1,n)cin>>ss[i];;cin>>tt;
memset(tre[1],0,sizeof tre[1]);
din=1;
rep(i,1,n){
int sz=ss[i].size(),pos=0;
rep(j,0,sz-1){
if(tre[pos][ss[i][j]-'a']==0){
tre[pos][ss[i][j]-'a']=++din;
memset(tre[din],0,sizeof tre[din]);
val[pos]=j;
pos=din;
}else pos=tre[pos][ss[i][j]-'a'];
}
}
//rep(i,1,din)rep(j,0,25)die[tre[i][j]]=i,pos[tre[i][j]]=j;;die[0]=0;
queue<int> q;
rep(i,0,25)if(tre[1][i])q.push(tre[1][i]),bac[tre[1][i]]=1;
while(!q.empty()){
int x=q.front();q.pop();
rep(i,0,25)if(tre[x][i]){
int y=tre[x][i];
bac[y]=tre[bac[x]][i];
}else tre[x][i]=tre[bac[x]][i]; //?
}
int len2=tt.size(),pos=0;
rep(i,0,len2-1){
pos=tre[pos][tt[i]-'a'];
for(int j=pos;j>=1;j=bac[j])ans[val[j]]++;
}
int ma=0;
rep(i,1,n)ma=max(ma,ans[i]);
cout<<ma<<endl;
rep(i,1,n)if(ma==ans[i])cout<<ss[i]<<endl;
}
return 0;
}
回复
共 5 条回复,欢迎继续交流。
正在加载回复...