于是你把我给杀死了

· · 题解

考虑 dp, f_{i, j} 表示长串比短串多的那段是 s_i 长为 j 的后缀，短串的长度最短是多少。枚举往短串加的字符串 s_k, 令 t=\min(len_{k}, j)，则要求 s_k 长为 t 的前缀与 s_i 从 len{i} - j 开始长为 j 的子串相等，这样才能使拼上之后仍然能匹配。转移有如下两种：

  1. 长串仍然更长，f_{i, j} \leftarrow f_{i, j - t}
  2. 短串更长了，f_{i, j} \leftarrow f_{k, len_{k} - j}, 不懂的可以画一下，比较显然。

转移有环怎么办？由于是求最小值，所以直接将转移建边，跑最短路即可。|V| = nm, |E| = n^2m

时间复杂度 \mathcal{O}(n^2m \log nm)。

吗？

如果是这样，那过不了加强版，但是加强版跑的飞快，为什么？

dijkstra 的时间复杂度为 \mathcal{O}(|E| \log |V|), 但其实 |E| 不是边数，而是总松弛次数，大多数情况总松弛次数就是边数，但是这道题不一样，边权 \le m, 假设当前堆中 dis 最小值是 d, 那么更新到的点的 dis \le d + m, 而最终这些点的 dis 也不会小于 d, 理由不知道的可以回去看 dijkstra 的原理，所以每个点最多松弛 m 次，总松弛次数为 \mathcal{O}(|V|m) = \mathcal{O}(nm^2)

时间复杂度 \mathcal{O}(n^2m^2 + nm^2 \log nm)。（其实 substr 复杂度是 \mathcal{O}(m) 的，然而我们可以根据 01 压位优化掉，但是我懒得写了）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 60, M = 2510, mod = 998244353;
template<typename T>
void dbg(const T &t) { cout << t << endl; }
template<typename Type, typename... Types>
void dbg(const Type& arg, const Types&... args) {
    cout << arg << ' ';
    dbg(args...);
}
int n, m, tot, id[N][N], f[M], len[N];
string s[N];
vector<pii>e[M];
int main() {
    // freopen("data.in", "r", stdin);
    // freopen("data.out", "w", stdout);
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        len[i] = (int)s[i].size();
        for (int j = 0; j < len[i]; j++) id[i][j] = ++tot;
    }
    for (int i = 1; i <= n; i++) 
        for (int j = 0; j < len[i]; j++) 
            for (int k = 1; k <= n; k++) {
                int t = min(len[k], j);
                if (s[k].substr(0, t) == s[i].substr(len[i] - j, t)) {
                    if (j < len[k]) {
                        e[id[i][j]].push_back({id[k][len[k] - j], t});
                    } else {
                        e[id[i][j]].push_back({id[i][j - t], len[k]});
                    }
                }
            }
    memset(f, 0x3f, sizeof f);
    set<string>st; priority_queue<pii, vector<pii>, greater<pii>>q;
    for (int i = 1; i <= n; i++) st.insert(s[i]);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < len[i]; j++) {
            string t = s[i].substr(0, j);
            if (st.count(t)) {
                f[id[i][len[i] - j]] = j;
                q.push({j, id[i][len[i] - j]});
            }
        }
    }
    while (!q.empty()) {
        auto [dis, u] = q.top(); q.pop();
        if (f[u] != dis) continue;
        for (auto [v, w] : e[u]) {
            if (f[v] > f[u] + w) {
                f[v] = f[u] + w;
                q.push({f[v], v});
            }
        }
    }
    int ans = 0x3f3f3f3f;
    for (int i = 1; i <= n; i++) ans = min(ans, f[id[i][0]]);
    cout << (ans == 0x3f3f3f3f ? -1 : ans) << '\n';
    return 0;
}

结束了吗？没有。

可以把堆换成桶，时间复杂度 \mathcal{O}(n^2m+nm^2)。代码我没写。