Question
给定 \(N\) 个字符串 \(S_1,S_2,\cdots, S_N\)
找到一个包含所有这些字符串作为子字符串的最小长度的字符串
一个字符串 \(S\) 包含一个字符串 \(T\) 作为子字符串是指:
如果 \(T\) 可以通过从 \(S\) 的开头删除零个或多个字符以及从末尾删除 \(0\) 个或多个字符而获得
Solution
先观察如果一个字符串的前缀等于另外一个字符串的后缀,那么就可以共用一些字符
用哈希算出两个字符串可以共用的字符数量 \(p[i][j]\),特别得,如果 \(j\) 是 \(i\) 的子串,\(p[i][j]\) 就是 \(j\) 的长度
求出 \(p[i][j]\) 后用状压 DP 来确定字符串的顺序
Code
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long LL;
struct Hash {
int p, mod;
Hash(int p, int mod) : p(p), mod(mod) {}
LL pow(LL a, LL b) {
LL ans = 1;
for (; b; b >>= 1, a = a * a % mod) if (b & 1) ans = ans * a % mod;
return ans;
}
vector<LL> get_hash(string &s) {
int n = s.size();
vector<LL> h(n + 1, 0);
h[0] = s[0] - 'a' + 1;
for (int i = 1; i < n; i++) {
h[i] = (h[i - 1] * p + s[i] - 'a' + 1) % mod;
}
return h;
}
LL get_sub_hash(vector<LL> &h, int l, int r) {
if (l == 0) return h[r];
return (h[r] - h[l - 1] * pow(p, r - l + 1) % mod + mod) % mod;
}
};
LL dp[21][1 << 20];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int n; cin >> n;
Hash hsh1(37, 1e9 + 7);
vector<string> s(n + 1);
vector<vector<LL> > h(n + 1);
for (int i = 1; i <= n; i++)
cin >> s[i], h[i] = hsh1.get_hash(s[i]);
vector<vector<int> > p(n + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= n; i++) // s[i] 在前 s[j] 在后
for (int j = 1; j <= n; j++) {
if (i == j) continue;
int flg = 0;
if (s[i].size() >= s[j].size()) {
for (int k = 0; k + s[j].size() - 1 < s[i].size(); k++ )
if (hsh1.get_sub_hash(h[i], k, k + s[j].size() - 1) == h[j][s[j].size() - 1]) {
p[i][j] = s[j].size();
flg = 1;
break;
}
}
if (flg) continue;
int cnt;
for (cnt = min(s[i].size(), s[j].size()) - 1; cnt >= 0; cnt--) {
LL A = hsh1.get_sub_hash(h[i], s[i].size() - 1 - cnt , s[i].size() - 1);
LL B = hsh1.get_sub_hash(h[j], 0, cnt);
if (A == B)
break;
}
p[i][j] = cnt + 1;
}
// for (int i = 1; i <= n; i++)
// for (int j = 1; j <= n; j++) {
// printf("%d%c", p[i][j], " \n"[j == n]);
// }
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= n; i++)
dp[i][1 << (i - 1)] = s[i].size();
for (int S = 0; S < (1<<n); S++) {
for (int i = 1; i <= n; i++) {
if ((S >> (i - 1) & 1) == 0) continue;
for (int j = 1; j <= n; j++) {
if (S >> (j - 1) & 1) continue;
if (p[i][j] == s[j].size())
dp[i][S | (1 << (j - 1))] = min(dp[i][S | (1 << (j - 1))], dp[i][S]);
else
dp[j][S | (1 << (j - 1))] = min(dp[j][S | (1 << (j - 1))], (LL)(dp[i][S] + s[j].size() - p[i][j]));
}
}
}
LL ans = INF;
for (int i = 1; i <= n; i++) ans = min(ans, dp[i][(1 << n) - 1]);
cout << ans << '\n';
return 0;
}
标签:cnt,int,题解,LL,Compress,ABC343,字符串,size,mod
From: https://www.cnblogs.com/martian148/p/18050346