洛谷题面传送门 & Atcoder 题面传送门

神仙题。

mol 一发现场（bushi）独立切掉此题的 ycx %%%%%%%

首先咱们可以想到一个非常 naive 的 DP，\(dp_{i,j}\) 表示在前 \(i\) 个字符串拼出的长度为 \(j\) 的字符串中，字典序的最小的串是什么，那么显然 \(dp_{i,j}\) 的转移就在 \(dp_{i-1,j-|s_i|}+s_i\) 和 \(dp_{i-1,j}\) 中比个大小即可，但是由于字符串字典序比大小，以及存储字符串均可达到线性复杂度，因此该做法时空复杂度均为 \(nk^2\)，一脸过不去的亚子。

不过注意到本题的一个性质，就是本题的 \(dp\) 采用的是字典序大小比较，考虑字典序比较的一个特性，就是对于某两个字符串的两个前缀 \(s,t(|s|<|t|)\)，如果 \(s,t\) 之间不存在前缀关系，那么不论再往 \(s,t\) 后面添加什么字符，这两个字符串的字典序已经定下来了。更进一步的，对于本题而言，对于两个 \(dp_{i,j}\) 和 \(dp_{i,k}\)，如果它们都能转移到 \(dp_{n,m}\)（即，在后 \(n-i\) 个字符串中，存在某个字符串的子集使其长度之和为 \(m-j\)，也存在某个字符串的子集使其长度之和为 \(m-k\)，这个可以通过一遍反着的背包预处理出来，处理完之后对于不能转移到 \(dp_{n,m}\) 的 \(dp_{i,j}\) 我们就直接跳过即可），如果 \(dp_{i,j}\) 与 \(dp_{i,k}\) 不存在前后缀关系，那么前 \(\min(j,k)\) 位字典序较大的字符串已经没有用了，因此我们考虑在求解 \(dp_{i,j}\) 时维护一个单调栈存储当前有用的位置集合，并且从栈顶到栈底下标依次递减，那么根据之前的分析，这些有用的位置的集合的 DP 值必然两两之间存在前后缀关系，也就是说，假设栈顶元素为 \(s\)，那么对于栈中的某个元素 \(t\)，一定有 \(dp_{i,t}\) 是 \(dp_{i,s}\) 长度为 \(t\) 的前缀，因此对于每一个 \(i\)，我们并不用记录所有这样的 \(dp_{i,j}\)，我们只用记录栈顶元素的 \(dp\) 值 \(fs_i\) 即可，这样对于一个 \(dp_{i,j}\) 有两种来源：

• \(dp_{i-1,j-|s_i|}+s_i\)，此时我们可以检验 \(dp_{i-1,j-|s_i|}\) 是否是有用的决策点，如果是那么我们就用 \(fs_{i-1}\) 长度为 \(j-|s_i|\) 的前缀与 \(s_i\) 拼接得到的字符串去更新 \(dp_{i,j}\)
• \(dp_{i-1,j}\)，类似于上面的情况。

那么怎么判断一个字符串是否是有用的决策点呢？我们考虑额外维护一个数组 \(st_{i,j}\) 表示 \(dp_{i,j}\) 的状态，如果 \(st_{i,j}=0\) 表示 \(dp_{i,j}\) 为无用决策点，如果 \(st_{i,j}=2\) 表示 \(dp_{i,j}\) 从 \(dp_{i-1,j-|s_i|}+s_i\) 比从 \(dp_{i-1,j}\) 转移更优，如果 \(st_{i,j}=1\) 表示 \(dp_{i,j}\) 从 \(dp_{i-1,j}\) 比从 \(dp_{i-1,j-|s_i|}+s_i\) 转移更优，不难发现根据 \(fs_{i-1}\) 和 \(st_{i,j}\) 可以求出 \(dp_{i,j}\)，这样空间就被我们成功地搞到了 \(\mathcal O(nm)\)。

还有一个问题就是怎样维护这样一个单调栈，假设我们已经求出了 \(dp_{i,j}\)，那么我们考虑栈顶元素 \(dp_{i,s}\)，分三种情况考虑：

• 如果 \(dp_{i,s}\) 是 \(dp_{i,j}\) 的前缀，那么 \(dp_{i,s}\) 和 \(dp_{i,j}\) 都是有用的决策点，因此此时我们可以直接 break 掉并将 \(j\) 压入单调栈。
• 如果 \(dp_{i,j}\) 前 \(s\) 位的字典序小于 \(dp_{i,s}\)，那么 \(dp_{i,s}\) 就没用了，将 \(st_{i,s}\) 设为 \(0\) 并不断弹出栈顶元素直至栈为空或不存在该情况为止。
• 如果 \(dp_{i,j}\) 前 \(s\) 位的字典序大于 \(dp_{i,s}\)，那么 \(dp_{i,j}\) 就没用了，直接退出并不将 \(j\) 压入栈中。

直接暴力进行字典序比较是 \(\mathcal O(nm^2)\) 的，还是无法通过此题，不过还是根据之前的性质：根据 \(fs_{i-1}\) 和 \(st_{i,j}\) 可以求出 \(dp_{i,j}\)。因此我们考虑能不能直接根据 \(st_{i,s}\) 和 \(fs_{i-1}\)，进行一些预处理 \(\mathcal O(1)\) 判断字典序大小呢？

答案是肯定的。

我们假设要对 \(dp_{i,j}\) 和 \(dp_{i,s}\) 比大小 \((j>s)\)，那么分情况讨论：

• \(st_{i,j}=st_{i,s}=1\)，那么显然它们都是 \(fs_{i-1}\) 的前缀，显然互为前缀关系
• \(st_{i,j}=1,st_{i,s}=2\)，那么 \(dp_{i,j}\) 为 \(fs_{i-1}\) 长度为 \(j\) 的前缀，\(dp_{i,s}\) 为 \(fs_{i-1}\) 长度为 \(s-|s_i|\) 的前缀拼上 \(s_i\)，因此我们只需检验 \(s_i\) 与 \(fs_{i-1}[s-|s_i|+1…j]\) 的大小关系即可。
• \(st_{i,j}=2,st_{i,s}=1\)，如果 \(s\le j-|s_i|\)，那么显然 \(dp_{i,s}\) 为 \(dp_{i,j}\) 的前缀，否则我们需要比较 \(fs_{i-1}[j-|s_i|+1…s]\) 与 \(s_i\) 的大小关系。
• \(st_{i,j}=2,st_{i,s}=2\)，那么我们要比较 \(fs_{i-1}[s+1…s]\) 与 \(s_i\) 的关系，相等的话进一步比较 \(s_i[s+|s_i|-j,…|s_i|]\) 与 \(s_i\) 的大小关系。

如果我们记 \(t_i=s_i+'\#'+fs_{i-1}\)，那么上述比较操作均可表示为比较一个前缀与一个子串的大小关系，可以通过比较第一个不相等的位置的字符判断，而由于我们想求的是一个前缀与一个子串的 LCP 的形式，因此可以考虑 Z 函数，这样即可实现 \(\mathcal O(1)\) 比较。

总复杂度 \(nm+\sum|s_i|\)

const int MAXN=2000;
const int MAXM=1e4;
const int MAXL=1e6;
int n,m,k,dp[MAXN+5][MAXM+5];
string s[MAXN+5],fs[MAXN+5];
bool can[MAXN+5][MAXM+5];
char t[MAXL*2+5];int z[MAXL*2+5];
void z_func(){
    int l=0,r=0;
    for(int i=2;i<=m;i++){
        z[i]=max(min(r-i+1,z[i-l+1]),0);
        while(i+z[i]<=m&&t[i+z[i]]==t[z[i]+1]) ++z[i];
        if(i+z[i]-1>r) l=i,r=i+z[i]-1;
    }
}
int getcmp(int l,int r,int x){//comparison between a prefix and a substring (1 prefix > substring)
    if(l>r) return (!x)?0:1;
    if(z[l]>=min(r-l+1,x)) return 0;
    return 1-((t[l+z[l]]>t[z[l]+1])<<1);
}
int main(){
    scanf("%d%d",&n,&k);can[n+1][0]=1;
    for(int i=1;i<=n;i++){
        static char str[MAXL+5];scanf("%s",str+1);
        int len=strlen(str+1);
        for(int j=1;j<=len;j++) s[i].pb(str[j]);
    }
    for(int i=n;i;i--) for(int j=0;j<=k;j++)
        can[i][j]=can[i+1][j]|((j<s[i].size())?0:can[i+1][j-s[i].size()]);
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        m=0;for(int j=0;j<s[i].size();j++) t[++m]=s[i][j];
        t[++m]='#';stack<int> stk;
        for(int j=0;j<fs[i-1].size();j++) t[++m]=fs[i-1][j];t[m+1]='\0';
        z_func();
        for(int j=0;j<=k;j++) if(can[i+1][k-j]){
            if(dp[i-1][j]&&j>=s[i].size()&&dp[i-1][j-s[i].size()])
                dp[i][j]=1+(getcmp(s[i].size()+2+j-s[i].size(),s[i].size()+1+j,s[i].size())<=0);
            else if(dp[i-1][j]) dp[i][j]=1;
            else if(j>=s[i].size()&&dp[i-1][j-s[i].size()]) dp[i][j]=2;
            if(dp[i][j]==1){
                while(!stk.empty()){
                    int x=stk.top();
                    if(dp[i][x]==1) break;
                    else{
                        int st=getcmp(s[i].size()+2+x-s[i].size(),s[i].size()+1+j,s[i].size());
                        if(st==0) break;if(st==1) stk.pop(),dp[i][x]=0;
                        if(!~st){dp[i][j]=0;goto end1;}
                    }
                } stk.push(j);
                end1:
                    ;
            } else if(dp[i][j]==2){
                while(!stk.empty()){
                    int x=stk.top();
                    if(dp[i][x]==2){
                        int st=getcmp(s[i].size()+2+x-s[i].size(),s[i].size()+1+j-s[i].size(),s[i].size());
                        if(!st){
                            int dif=j-x+1;
                            if(z[dif]+dif==s[i].size()+1) st=0;
                            else st=1-((t[z[dif]+dif]<t[z[dif]+1])<<1);
                        } if(st==1) stk.pop(),dp[i][x]=0;if(!st) break;
                        if(!~st){dp[i][j]=0;goto end2;}
                    } else {
                        if(x<=j-s[i].size()) break;
                        else{
                            int st=getcmp(s[i].size()+2+j-s[i].size(),s[i].size()+1+x,s[i].size());
                            if(st==0) break;if(!~st) stk.pop(),dp[i][x]=0;
                            if(st==1){dp[i][j]=0;goto end2;}
                        }
                    }
                } stk.push(j);
                end2:
                    ;
            }
        }
        if(!stk.empty()){
            fs[i]=(dp[i][stk.top()]==1)?fs[i-1].substr(0,stk.top()):
            fs[i-1].substr(0,stk.top()-s[i].size())+s[i];
        } else fs[i]=fs[i-1];
    } for(int i=0;i<k;i++) putchar(fs[n][i]);
    return 0;
}
/*
5 6
aba
bab
bba
aab
bab

7 7
aa
aabb
a
bbaa
bba
babab
aa
*/