社区讨论

蒟蒻刚写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 条回复,欢迎继续交流。

正在加载回复...