感觉不是特别困难（？），思路歪了没想出来。
主要是想后缀转移，实际上这个想法很蠢，因为这样相比前缀转移很难做字典序的比较，而且不存在对状态剪枝的好性质了。
字典序题最好前缀后缀都想一遍吧。。。
题意
给定 \(N\) 个字符串 \(S_1, \ldots, S_N\) 和一个整数 \(K\)，你需要选择一个子序列 \(i_1, i_2, \ldots, i_m\)，使得：
- \(i_1 < i_2 < \ldots < i_m\)，
- 设 \(T = S_{i_1} + S_{i_2} + \ldots + S_{i_m}\)，\(|T| = K\)，
- 在所有可能的方案中，\(T\) 字典序最小。
输出 \(T\)。
\(1 \le N \le 2000, 1 \le K \le 10^4\)。
思路
首先有一个简单的暴力，设 \(dp(i, j)\) 表示前 \(i\) 个字符串总长为 \(j\)，字典序最小的串是什么。总时间复杂度 \(O(NK^2)\)，因为字符串比较是 \(O(K)\) 的。
考虑优化，首先因为状态总空间是 \(O(NK^2)\) 的，要尝试剪掉多余的状态。第一个观察就是，如果 \(i + 1 \sim N\) 凑不出来 \(K - j\) 的长度，那 \(dp(i, j)\) 肯定没用。但这个观察不够强。第二个观察就是，在有用的 \(j\) 中，如果 \(dp(i, j)\) 和 \(dp(i, k)\) 存在某一位不同，那字典序更大的就没用了。这个观察是很强的，它给的性质就是任意有用的 \(j, k\)，假设 \(j < k\)，一定满足 \(dp(i, j)\) 是 \(dp(i, k)\) 的前缀。
那就可以对每个 \(i\) 维护一个母串 \(T_i\)，每个 \(dp(i, j)\) 都是 \(T_i\) 的一个前缀。接下来考虑转移，假设转移 \(dp(i, j)\)，它的取值为 \(\min\{dp(i - 1, j), dp(i - 1, j - |S_i|) + S_i\}\)，如果 \(dp(i - 1, j)\) 或 \(dp(i - 1, j - |S_i|)\) 不是 \(T_{i - 1}\) 的前缀，直接取是 \(T_{i - 1}\) 前缀的那个就行了。否则，就相当于在比较 \(T_{i - 1}\) 的某个子串与 \(S_i\) 的字典序大小，可以 Z 函数或哈希求。
接着考虑求出 \(T_i\)，由于空间不够，我们只能求出 \(dp(i, j)\) 的选择。从小到大枚举 \(j\)，用一个栈更新 \(T_i\)，从栈顶到栈底分别是有用的递减的 \(j\)。每次加入一个 \(dp(i, j)\)，如果 \(dp(i, j) > dp(i, top)\)，则跳过 \(j\)，否则一直弹出栈顶使得 \(dp(i, top)\) 是 \(dp(i, j)\) 的前缀，接着往栈中压入 \(j\) 即可。
如何比较呢？比较一定形如 \(S_i\) 的后缀与 \(S_i\) 的前缀比较，或 \(S_i\) 与 \(T_i\) 的某个字串比较，用 Z 函数或哈希同样可以解决。
时间复杂度 \(O(NK + \sum |S_i|)\)。
字符串题细节好多（悲），代码写了依托：
#include <bits/stdc++.h>using i64 = long long;
using namespace std;constexpr int N = 2E3 + 5, K = 1E4 + 5;int n, k, len[N];
string s[N];
string t[N];bitset<K> suf[N];int dp[N][K], z[K * 2];void getz(int n, const string &s) {for (int i = 2, l = 1, r = 1; i <= n; ++i) {if (i < r && z[i - l + 1] < r - i) {z[i] = z[i - l + 1];} else {z[i] = max(0, r - i);for (; i + z[i] <= n && s[i + z[i]] == s[z[i] + 1]; ++z[i]);}if (i + z[i] > r) {l = i;r = i + z[i];}}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> k;for (int i = 1; i <= n; ++i) {cin >> s[i];len[i] = s[i].size();}suf[n + 1].set(0);for (int i = n; i >= 1; --i) {suf[i] = suf[i + 1] | (suf[i + 1] << len[i]);}t[0] = "";for (int j = 1; j <= k; ++j) {dp[0][j] = -1;}for (int i = 1; i <= n; ++i) {string P = s[i] + '|' + t[i - 1];int L = P.size();P = '#' + P;getz(L, P);stack<int> stk;for (int j = 0; j <= k; ++j) {if (!suf[i + 1][k - j] || j - len[i] > (int)t[i - 1].size()) {dp[i][j] = -1;continue;}auto comp = [&](int p) {int lcp = z[len[i] + 2 + p];if (lcp == len[i]) {return 0;}if (p + lcp == t[i - 1].size()) {return 1;}return (t[i - 1][p + lcp] < s[i][lcp] ? -1 : 1);};if (j < len[i]) {if (dp[i - 1][j] == -1) dp[i][j] = -1;else dp[i][j] = 1;} else {if (dp[i - 1][j] == -1 && dp[i - 1][j - len[i]] == -1) {dp[i][j] = -1;continue;}if (dp[i - 1][j] == -1) {dp[i][j] = (comp(j - len[i]) != -1 ? 2 : -1);} else if (dp[i - 1][j - len[i]] == -1) {dp[i][j] = 1;} else {if (comp(j - len[i]) != 1) {dp[i][j] = 1;} else {dp[i][j] = 2;}}}if (dp[i][j] == -1) continue;while (!stk.empty()) {int top = stk.top();if (dp[i][top] == 1) {if (dp[i][j] == 1 || j - len[i] >= top) {stk.push(j);break;}int lcp = z[j + 2];if (lcp < top + len[i] - j) {dp[i][top] = -1;stk.pop();} else {stk.push(j);break;}} else {int plcp = z[top + 2];if (dp[i][j] == 1 || top + plcp <= j) {if (plcp == len[i]) {stk.push(j);} else {dp[i][j] = -1;}break;}int c = top + len[i] - j;int lcp = z[len[i] - c + 1];if (lcp == c) {stk.push(j);break;}if (s[i][len[i] - c + lcp] > s[i][lcp]) {dp[i][top] = -1;stk.pop();} else {dp[i][j] = -1;break;}}}if (stk.empty()) {stk.push(j);}}assert(!stk.empty());int top = stk.top();if (dp[i][top] == 1) {t[i] = t[i - 1].substr(0, top);} else {t[i] = t[i - 1].substr(0, top - len[i]) + s[i];}for (int i = 1; i <= P.size(); ++i) z[i] = 0;}assert(t[n].size() == k);cout << t[n] << "\n";return 0;
}