题意
给你 \(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 秒非常宽松，🐣🐣！文章来源：https://www.toymoban.com/news/detail-837707.html
实现
这份代码在作者写这篇题解的时候还是 atc 全站最优解。文章来源地址https://www.toymoban.com/news/detail-837707.html
#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;
}
到了这里，关于abc343G 题解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
