CF1200E Compress Words

传送门

Solution

设当前待合并的串为 $A$，已合并的串为 $B$。若 $|A|\ge |B|$，则 $C=A+B$。否则 $C$ 等于 $A$ 与 $B$ 长度为 $|A|$ 的后缀拼接而成的字符串。对 $C$ 进行 KMP，求出最大相同前后缀长度 $nxt_{|C|}$。把 $A$ 的相应长度后缀并入 $B$ 后面即可。

为防止出现错误，可以在 $A$、$B$ 中间插入字符 #。

时间复杂度 $O(\sum |s_i|)$

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, nxt[2000010];
string s, ans;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        cin >> s;
        if (i == 1) {
            ans = s;
            continue;
        }
        string str; int k = 0, len = s.size();
        s += "#";
        if (len < ans.size())
            str = s + ans.substr(ans.size() - len, len);
        else 
            str = s + ans;
        nxt[0] = nxt[1] = 0;
        for (int j = 1; j < str.size(); j++) {
            while (k > 0 && str[k] != str[j])
                k = nxt[k - 1];
            if (str[k] == str[j])
                ++k;
            nxt[j] = k;
        }
        ans += s.substr(nxt[str.size() - 1], len - nxt[str.size() - 1]);
    }
    cout << ans << endl;
    return 0;
}