WA#8 求调
查看原帖
WA#8 求调
747542
20110422tnm楼主2025/7/25 11:24
#include <bits/stdc++.h>
#define lint long long
using namespace std;
const int N=1005000;
int n,T,st[N];
struct tree{
	int fail,end,vis[40];
}t[N];
int cnt=0;
void build(string &s,int i){
	int len=s.size();
	int now=0;
	for(int i=0;i<len;i++){
		int x=s[i]-'A';
		if(!t[now].vis[x])
			t[now].vis[x]=++cnt;
		now=t[now].vis[x];
	}
	st[now]|=1<<(i-1);
}
void getfail(){
	queue<int> q;
	for(int i=0;i<26;i++){
		if(t[0].vis[i]!=0){
			t[t[0].vis[i]].fail=0;
			q.push(t[0].vis[i]);
		}
	}
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			if(t[x].vis[i]!=0){
				t[t[x].vis[i]].fail=t[t[x].fail].vis[i];
				st[t[x].vis[i]]|=st[t[t[x].fail].vis[i]];
				q.push(t[x].vis[i]);
			}else{
				t[x].vis[i]=t[t[x].fail].vis[i];
			}
		}
	}
}
string s;
struct A{
	int a,b;
};
queue<A> q;
int c[N],tot,nod,fa[N],ans[N];
bool vis[605][1<<12|1];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s;
		build(s,i);
	}
	getfail();
	q.push({0,0});
	vis[0][0]=1;
	int bh=0;
	while(!q.empty()){
		A x=q.front();
		q.pop();
		if(x.b==((1<<n)-1)){
			while(bh){
				c[++nod]=ans[bh];
				bh=fa[bh];
			}
			for(int i=nod;i>=1;i--)
				putchar(c[i]+'A');
			return 0;
		}
		for(int i=0;i<26;i++){
			int y=t[x.a].vis[i];
			if(!vis[y][x.b|st[y]]){
				vis[y][x.b|st[y]]=1;
				q.push({y,x.b|st[y]});
				fa[++tot]=bh;
				ans[tot]=i;
			}
		}
		++bh;
	}
	return 0;
}
2025/7/25 11:24
加载中...