自动搬运

查看原文

来自洛谷，原作者为

	Forever1507 不拿金勾不改个性签名||菜

搬运于2025-08-24 21:53:42，当前版本为作者最后更新于2022-10-14 17:39:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

爆搜就行了，对，就是爆搜。

考虑此时你手上有俩字符串 $s_1,s_2$（不妨设前者更长），那么要是能够继续往后拼答案，$s_2$ 必须是 $s_1$ 的前缀，因为长度只有 $20$，直接暴力匹配。

然后设 $s'$ 为在 $s_1$ 前面砍掉 $s_2$ 之后的答案，那么这个东西就显然是另一个字符串的前缀，或者另一个字符串是它的前缀，$n$ 只有 $20$，枚举即可。

那么，只要在最开始枚举两个串，使得其中一个是另一个的前缀，以它们为 $s_1$ 和 $s_2$ 开搜，答案取最小即可，搜到相等之后维护答案。

当然直接这么搜会寄，加一个比较强的剪枝：

当前的这两个串的长度若超过已有最小值，停下来，不搜了，反正对答案没贡献。

还有一个细节，初始答案设 $10^9$ 会爆栈+超时，虽然不会证明，但是答案很难给你构造得超过所有串的总长（即 $400$），不行的话你设 $10^3$ 都行，最大差不多开到 $9000$ 都没事。（所以这个做法之后也有可能被 hack，或者谁要是能提供严谨证明麻烦私一下）

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
string s[25];
string ans;
int len=400;
bool cmp(string s1,string s2){
	return s1.size()>s2.size();
}
void dfs(string s1,string s2){//s1长
	if(s1.size()>len||s2.size()>len)return;//大力剪枝
	if(s1.size()==s2.size()){
		if(len>s1.size()){
			len=s1.size();//更新答案
			if(ans==""||ans.size()>s1.size())ans=s1;
			else ans=min(ans,s1);
		}
		return;
	} 
	if(s1.size()<s2.size())swap(s1,s2);//保证s1更长
	int m=s1.size()-s2.size();
	for(int i=1;i<=n;++i){
		if(s[i].size()>=m){//s'是s[i]的前缀
			string _s="";
			for(int i=s2.size();i<s1.size();++i)_s+=s1[i];
			if(s[i].substr(0,m)==_s)dfs(s1,s2+s[i]);
		}
		else{//反之
			if(s1.substr(s2.size(),s[i].size())==s[i])dfs(s1,s2+s[i]);
		}
	}
	return;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;++i)cin>>s[i];
	sort(s+1,s+n+1,cmp);//按长度排序，不然substr会挂
	for(int i=1;i<=n;++i){
		for(int j=i+1;j<=n;++j){
			if(s[i].substr(0,s[j].size())==s[j]){
				dfs(s[i],s[j]);
			}
		}
	}
	cout<<len<<'\n'<<ans;
	return 0;
}