WA #9 求调
查看原帖
WA #9 求调
562569
kingho11楼主2025/2/4 20:40
#include<bits/stdc++.h>
using namespace std;
const int N=15,SLEN=15*50+5;
int n,tr[SLEN][30],tot=1,fail[SLEN],flag[SLEN],cntt=0,num;
string s[N],ans,p;
bool vis[SLEN][9000]; 
vector <int> v[SLEN];
void insert(int id)
{
	int u=1;
	for(int i=0;i<s[id].length();i++)
	{
		if(!tr[u][s[id][i]-'A'])
		{
			tr[u][s[id][i]-'A']=++tot;
			v[u].push_back(tot);
		}
		u=tr[u][s[id][i]-'A'];
	}
	if(flag[u])
	{
		cntt++;
		return ;
	}
	flag[u]=++num;
}
void build()
{
	for(int i=0;i<26;i++) tr[0][i]=1;
	queue <int> q;
	q.push(1);
	fail[1]=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<26;i++)
		{
			if(tr[u][i])
			{
				q.push(tr[u][i]);
				int o=fail[u];
				while(o && !tr[o][i]) o=fail[o];
				fail[tr[u][i]]=tr[o][i];
				v[tr[u][i]].push_back(tr[o][i]);
			}
		}
	}
}
struct uuu{
	int u,zt;
	string ans;
};
void bfs()
{
	queue <uuu> q;
	q.push((uuu){1,0,""});
	string rans="-";
	bool fl=0;
	while(!q.empty())
	{
		int siz=q.size();
		for(int p=0;p<siz;p++)
		{
			int u=q.front().u,zt=q.front().zt;
			string anss=q.front().ans;
			if(zt==(1<<(n-cntt))-1)
			{
				if(rans=="-") rans=anss;
				else rans=min(rans,anss);
				fl=1;
			}
			q.pop();
			if(fl) continue;
			for(int i=0;i<26;i++)
			{
				if(tr[u][i])
				{
					int v2=tr[u][i];
					int o=fail[v2],ztt=zt;
					if(flag[v2]) ztt|=(1<<(flag[v2]-1));
					for(;o>=1;o=fail[o])
					{
						if(flag[o])
						{
							ztt|=(1<<(flag[o]-1));
						}
					}
					o=fail[v2];
					for(;o>=1;o=fail[o])
					{
						if(vis[o][ztt]) continue;
						vis[o][ztt]=1;
						q.push((uuu){o,ztt,anss+(char)(i+'A')});
					}
					if(vis[v2][ztt]) continue;
					vis[v2][ztt]=1;
					q.push((uuu){v2,ztt,anss+(char)(i+'A')});
				}
			}
		}
		if(fl)
		{
			cout<<rans;
			return ;
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
		insert(i);
	}
	build();
	bfs();
}
2025/2/4 20:40
加载中...