题意

给你 \(N\) 个由小写字母组成的字符串 \(S_1, S_2, \ldots, S_N\)，找出一个母串使得它包含所有这些字符串作为它的子串，最小化该母串的长度并输出。

\(1 \leq N \leq 20\)，\(\sum |S_i| \leq 2 \times 10 ^ 5\)

（没错洛谷翻译就是我写的）

思路

首先如果有一个字符串被另一个字符串完全包括，那么直接把被包括的字符串删了显然是不影响答案的。

对于剩下的字符串，直接把所有字符串拼接在一起形成母串肯定可行，但假如我们有两个字符串，前一个字符串的后缀和后一个的字符串前缀有一段匹配，那么将后一个字符串的这段前缀删去再加入显然也是合法的母串，所以我们可以贪心删最长匹配。

我们设 \(l_i\) 为第 \(i\) 为 \(S_i\) 的长度，\(d(i, j)\) 为第 \(j\) 个字符串拼接在第 \(i\) 个字符串后面时最少需要额外追加的字符数量，按照刚才的思路 \(d(i, j)\) 就等于 \(l_j\) 减去 \(S_i\) 的后缀与 \(S_j\) 的前缀的最长匹配。那么该如何计算这个最长匹配呢？当然可以使用 exkmp。对于每对 \((i, j)\)，因为最长匹配长度 \(\leq \min(l_i, l_j)\)，所以直接枚举最长匹配可能的取值再用哈希判断复杂度就对了，\(O(n^2 + n \sum l_i)\)。

现在问题就被转换成了如果 \(S_i\) 成为母串开头的字符串，那么母串会增加 \(l_i\) 长度。如果 \(S_j\) 要接在 \(S_i\) 后面，母串最少会增加 \(d(i, j)\) 长度。还是问你母串最短能是多少。

那直接把每个字符串看成一个点，\(d(i, j)\) 看成 \(i\) --> \(j\) 的一条边的边权，从第 \(i\) 个点出发初始有 \(l_i\) 的代价，那么经过所有点恰好一次的通路的最小代价就是母串的最短长度。不难发现实际上就是经典的 TSP 问题，状压 dp 解决之。这部分时间复杂度为 \(O(n^2 \times 2^n)\)，所以总复杂度就是 \(O(n^2 + n \sum l_i + n^2 \times 2^n)\)，5 秒非常宽松，🐣🐣！

实现

这份代码在作者写这篇题解的时候还是 atc 全站最优解。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

template <class T>
inline void cmin(T &a, const T &b) {
    if (a > b) {
        a = b;
    }
}

const int N = 20, M = 2e5 + 1, Base = 29;

char str[M + 1]; int len[N];
unsigned powBase[M], hashy[N][M];

int dis[N][N], dp[1 << N][N];

int main(int argc, const char * argv[]) {
    powBase[0] = 1;
    for (int i = 1; i < M; ++i) {
        powBase[i] = powBase[i - 1] * Base;
    }
    
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%s", str + 1);
        len[i] = (int)strlen(str + 1);
        for (int j = 1; j <= len[i]; ++j) {
            hashy[i][j] = hashy[i][j - 1] * Base + str[j] - 'a' + 1;
        }
    }
    int del = 0;
    for (int i = 0; i < n; ++i) if (!(del & 1 << i)) {
        for (int j = 0; j < n; ++j) if (i != j && !(del & 1 << j)) {
            int leni = len[i], lenj = len[j];
            for (int k = 1; k <= leni - lenj + 1; ++k) {
                if (hashy[i][k + lenj - 1] - hashy[i][k - 1] * powBase[lenj] == hashy[j][lenj]) {
                    del |= 1 << j;
                    break;
                }
            }
            if (del & 1 << j) {
                continue;
            }
            for (int k = lenj - 1; k >= 0; --k) {
                if (hashy[j][k] == hashy[i][leni] - hashy[i][leni - k] * powBase[k]) {
                    dis[i][j] = lenj - k;
                    break;
                }
            }
        }
    }
    int undel[N], r = 0;
    for (int i = 0; i < n; ++i) if (!(del & 1 << i)) {
        undel[r++] = i;
    }
    n = r;
    int all = (1 << n) - 1;
    for (int i = 1; i <= all; ++i) {
        memset(dp[i], 127, sizeof(int) * (n + 1));
    }
    for (int i = 0; i < n; ++i) {
        dp[1 << i][i] = len[undel[i]];
    }
    for (int state = 1; state < all; ++state) {
        for (int i = state; i; i &= i - 1) {
            int pi = __builtin_ctz(i);
            for (int j = all ^ state; j; j &= j - 1) {
                int pj = __builtin_ctz(j);
                cmin(dp[state | 1 << pj][pj], dp[state][pi] + dis[undel[pi]][undel[pj]]);
            }
        }
    }
    printf("%d\n", *min_element(dp[all], dp[all] + n));
    return 0;
}

热门相关：君归矣   士子风流   名门贵妻：暴君小心点   唐朝小官人   我和超级大佬隐婚了