AT_abc343_g [ABC343G] Compress Strings

思路

首先假设有两个串 $a,b$，如果 $b$ 是 $a$ 的子串，且 $a \neq b$ 则不需要考虑 $b$；如果 $a = b$，则如需要保留一个 $a$。

做完上述操作后，显然最终的答案是由这些串按照一定顺序拼接起来，再删掉重叠部分。

例如：abbcc 与 ccdde 拼接为 abbccccdde，发现 cc 是重复的，所以删掉重叠部分为 abbccde。

显然我们可以使用 KMP 在 $\Theta(n^2 \cdot |S|)$ 的复杂度内求解出任意两个串 $s_i,s_j$ 的重叠部分，记作 $num_{i,j}$。

于是就变成了经典状压，我们定义 $dp_{st,i}$ 表示选取串的集合表示为 $st$，且最后选的一个串为 $s_j$。

然后就是经典状压转移了。

Code

#include <bits/stdc++.h>
#define re register

using namespace std;

const int N = 24,M = 4e5 + 10,K = (1 << 20) + 10,inf = 0x3f3f3f3f;
int n,m,ans = inf;
int nxt[M],len[N];
int num[N][N],dp[K][N];
string t[N],s[N];
unordered_map<string,bool> vis;

inline int kmp(string a,string b){
    string s = a + '&' + b; int len = s.length();
    for (re int i = 0;i < len;i++) nxt[i] = 0;
    for (re int i = 1,j = 0;i < len;i++){
        while (j && s[i] != s[j]) j = nxt[j - 1];
        if (s[i] == s[j]) j++;
        nxt[i] = j;
    }
    return nxt[len - 1];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    memset(dp,inf,sizeof(dp));
    cin >> n;
    for (re int i = 1;i <= n;i++) cin >> t[i];
    for (re int i = 1;i <= n;i++){
        for (re int j = 1;j <= n;j++){
            if (i == j) continue;
            if (t[j].find(t[i]) != string::npos && t[i] != t[j]) goto End;
        }
        if (vis.count(t[i])) continue;
        vis[t[i]] = true;
        s[++m] = t[i]; len[m] = t[i].length();
        End:;
    }
    n = m;
    for (re int i = 1;i <= n;i++){
        for (re int j = 1;j <= n;j++){
            if (i != j) num[i][j] = kmp(s[j],s[i]);
        }
    }
    for (re int st = 1;st < (1 << n);st++){
        int cnt = __builtin_popcount(st);
        if (cnt == 1){
            int x;
            for (re int i = 0;i < n;i++){
                if ((st >> i) & 1){
                    x = i + 1; break;
                }
            }
            dp[st][x] = len[x];
        }
        for (re int i = 0;i < n;i++){
            if (!((st >> i) & 1)) continue;
            for (re int j = 0;j < n;j++){
                if ((st >> j) & 1) continue;
                dp[st | (1 << j)][j + 1] = min(dp[st | (1 << j)][j + 1],dp[st][i + 1] + len[j + 1] - num[i + 1][j + 1]);
            }
        }
    }
    for (re int i = 1;i <= n;i++) ans = min(ans,dp[(1 << n) - 1][i]);
    printf("%d\n",ans);
    return 0;
}