DDOSvoid's Blog

CF 1200E Compress Words

发表于 分类于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/problemset/problem/1200/E

简要题意：给定 $n$ 个字符串，现在要合并这 $n$ 个字符串，对于第 $i$ 个加入的字符串，我们会删掉这个字符串的最长的一个和前 $i-1$​ 个已经合并好的字符串的后缀相等的前缀，求最后合并好的字符串

$n\le 10^5,len\le 10^6$​​

Solution

我们发现这个东西有点像是 $border$​，我们考虑将两个串都翻转一下，发现正好是求 $border$

注意到这个 $border$​ 不能超过第一个串的长度，我们在两个串之间加一个特殊字符即可避免

时间复杂度 $O(len)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <cstring>
#define maxn 1000010
#define ll long long
using namespace std;

int n, k;
char s[maxn], c[maxn], ans[maxn];

int nxt[maxn]; 
void init_nxt(char *s) {
    int k = 0, t = 0, n = strlen(s + 1); nxt[1] = 0; 
    for (int i = 2; i <= n; ++i) {
        while (k && s[k + 1] != s[i]) k = nxt[k];
        if (s[k + 1] == s[i]) ++k;
        nxt[i] = k; 
    }
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; cin >> ans + 1; k = strlen(ans + 1); 
    for (int o = 2; o <= n; ++o) {
        cin >> s + 1; int len = strlen(s + 1), t = 0;
        for (int i = 1; i <= min(len, k); ++i) c[++t] = ans[k - i + 1]; c[++t] = '$';
        for (int i = 1; i <= len; ++i) c[++t] = s[len - i + 1];
        c[t + 1] = 0; init_nxt(c);
        for (int i = nxt[t] + 1; i <= len; ++i) ans[++k] = s[i];
    } ans[k + 1] = 0; cout << ans + 1 << "\n";
    return 0; 
}