AC自动机无法ACAC自动机的题,91pts,WAon#4球调
查看原帖
AC自动机无法ACAC自动机的题,91pts,WAon#4球调
1371820
_Douglas_MacArthur楼主2025/7/31 17:16
#include<bits/stdc++.h>
using namespace std;
struct node{
	char c;
	int nxt[36],po,fa,shi;
}tr[1919810];
int n,m,cn,z,cc,x,k[15000],g[1919810],ans[114514],ct,in[1145],ma;
string a[1145],b;
queue<int>q;
char c;
string ci(){
//	c=' ';
	string f;
	while(c<'a'||c>'z'){
		c=getchar();
	}
	while(c>='a'&&c<='z'){
		f+=c;
		c=getchar();
	}
	return f;
}
void add(string s,int cixu){
	int z=s.size(),o=0;
	for(register int i=0;i<z;++i){
		if(!tr[o].nxt[s[i]-'a'+1]){
			++cn;
			tr[o].nxt[s[i]-'a'+1]=cn;
			tr[cn].fa=o;
			tr[cn].c=s[i];
			o=cn;
		}
		else{
			o=tr[o].nxt[s[i]-'a'+1];
		}
	}
	tr[o].po=cixu;
}
void shipeimima(){
	int v;
	for(int i=1;i<=26;i++){
		v=tr[0].nxt[i];
		if(v){
			q.push(v);
//			tr[v].shi=0;
		}
	}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		if(tr[u].fa){
			tr[u].shi=tr[tr[tr[u].fa].shi].nxt[tr[u].c-'a'+1];
		}
		for(int i=1;i<=26;i++){
			v=tr[u].nxt[i];
			if(v){
				q.push(v);
			}
			else{
				tr[u].nxt[i]=tr[tr[u].shi].nxt[i];
			}
		}
	}
}
int main(){
//	freopen("P3808_2.in","r",stdin);
//	freopen("P3808_1.out","w",stdout);
	while(1){
		cin>>n;
		if(!n){
			break;
		}
		for(int i=1;i<=n;i++){
			a[i]=ci();
			add(a[i],i);
		}
		b=ci();
		z=b.size();
		shipeimima();
		for(register int i=0;i<z;i++){
			x=tr[x].nxt[b[i]-'a'+1];
			for(register int j=x;j;j=tr[j].shi){
				if(tr[j].po){
					g[j]++;
					if(g[j]>ma){
						ct=1;
						ans[1]=tr[j].po;
						in[tr[j].po]=g[j];
						ma=max(g[j],ma);
					}
					else if(g[j]==ma&&in[tr[j].po]<g[j]){
						++ct;
						ans[ct]=tr[j].po;
						in[tr[j].po]=g[j];
					}
				}
			}
		}
		sort(ans,ans+ct+1);
		printf("%d\n",ma);
		for(int i=1;i<=ct;i++){
			cout<<a[ans[i]]<<endl;
		}
		for(int i=0;i<=cn;i++){
			tr[i].c='\0';
			for(int j=1;j<=26;j++){
				tr[i].nxt[j]=0;
			}
			tr[i].fa=0;
			tr[i].po=0;
			tr[i].shi=0;
			g[i]=0;
		}
		cn=0;
		ct=1;
		ma=0;
		memset(ans,0,sizeof(ans));
		memset(in,0,sizeof(in));
	}
	return 0;
}

2025/7/31 17:16
加载中...