P3881

Forever1507 · 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;
}