嘘~ 正在从服务器偷取页面 . . .

[ABC343G] Compress Strings 题解

发布日期: 2024-06-12

更新日期: 2024-06-12

文章字数: 720

[ABC343G] Compress Strings 题解

题意：

给你 $N$ 个由小写字母组成的字符串 $S_1, S_2, \ldots, S_N$ 。

找出一个母串使得它包含所有这些字符串作为它的子串，最小化该母串的长度并输出。

数据范围：$1 \leq N \leq 20,~\sum |S_i| \leq 2 \times 10 ^ 5$ 。

考虑状压dp。首先记 $a_{i,j}$ 为 $i,j$ 的最长公共子串的长度，这个可以用 kmp 跑出来。

设 $f(i,S)$ 为当前选了 $S$ 的字符串，最后一个选的字符串是 $i$ 时的最小值。

这里要求 $S$ 中的字符串不存在相互包含的情况，也可以用 kmp 跑出来。

那么

$f(j, S \cup \{j\}) \,\operatorname{\big\downarrow}\, f(i,S) + \operatorname{len} i - a_{i,j}$

上式 $\downarrow$ 表示取 min，边界 $f(i,\{j\}) = \operatorname{len} i$ 。

时间复杂度 $\mathcal{O}(n^2 \sum |S_i| + n^22^n)$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define INF 0x3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(21))
#define M ((int)(4e5 + 15))

char ok[N];
int n, a[N][N], f[N][1 << N], fail[M], len[N];
int solve(string s1, string s2, int type = 1)
{
    string s = '$' + s1 + s2; fail[0] = 0;
    for(int i = 2; i < s.size(); i++)
    {
        int j = fail[i - 1];
        while(j > 0 && s[j + 1] != s[i]) j = fail[j];
        if(s[j + 1] == s[i]) fail[i] = j + 1; else fail[i] = 0;
        if(type == 1 && i >= 2 * s1.size() && fail[i] >= s1.size()) return s1.size();
    }
    return type == 1 ? 0 : fail[s.size() - 1];
}
string s[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> s[i];
    sort(s + 1, s + 1 + n); n = unique(s + 1, s + 1 + n) - s - 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) if(i != j && solve(s[j], s[i])) ok[j] = 1;
    int o = 0; for(int i = 1; i <= n; i++) if(!ok[i]) { s[++o] = s[i]; } n = o;
    for(int i = 1; i <= n; i++) len[i] = s[i].size();
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) if(i != j)
        {
            a[i][j] = solve(s[j], s[i], 2);
            if(!a[i][j]) a[i][j] = solve(s[j], s[i]);
        }
    memset(f, 0x3f, sizeof(f));
    for(int i = 1; i <= n; i++) f[i][1 << (i - 1)] = len[i];
    const int mx = 1 << n;
    for(int S = 0; S < mx; S++)
        for(int i = 1; i <= n; i++) if(S & (1 << (i - 1)))
            for(int j = 1; j <= n; j++) if(!(S & (1 << (j - 1))))
                down(f[j][S | (1 << (j - 1))], f[i][S] + len[j] - a[i][j]);
    int res = INF;
    for(int i = 1; i <= n; i++) down(res, f[i][mx - 1]);
    cout << res << '\n';
    return 0;
}