Compress Words

发表于 分类于 ，

    给出n个字符串，字符串会逐个两两合并。

    合并的规则：选择一个最大的len，且满足前一个字符串的后缀len且等于后一个字符串的前缀len，将这部分合并。

    输出最终合并结果。

Compress Words

Created by LXC on Wed Sep 6 16:33:00 2023

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

ranting: 2000

tag: brute force, hashing, implementation, string suffix structures, strings

problem

给出n个字符串，字符串会逐个两两合并。

合并的规则：选择一个最大的len，且满足前一个字符串的后缀len且等于后一个字符串的前缀len，将这部分合并。

输出最终合并结果。

solution

字符串哈希，字符串的所有子串的哈希值获取与比较只需$O(1)$的时间。

每个串只会比较一次所有前缀，总时间复杂度是$O(n)$

如果出现哈希冲突导致wa，可以多重哈希。

code

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 1000005
using namespace std;

#define ull unsigned long long
const ull MOD = 998244353, BASE = 171;

// string s[] index from 0 to n-1
// B[i] = BASE^i
// s[i...j] = s[0...j] - s[0...i-1]
// hash s[0...i-1] = H[i] = s[0]*B[i-1]+s[1]*B[i-2]+...+s[i-1]*B[0]
// hash s[0...j] = H[j+1] = s[0]*B[j]+s[1]*B[j-1]+...+s[j]*B[0]
// hash s[i...j] = H[j+1] - H[i]*B[j-i+1]
// hash s[i...j-1] = H[j] - H[i]*B[j-i]
// for (int i=1; i<=n; i++) {
//     H[i] = (H[i-1]*BASE%MOD + s[i-1])%MOD;
// }

ull H[N], B[N];

void sol() {
    auto hash = [&](int l, int r) {  // hash of s[l...r-1]
        return (H[r] - H[l] * B[r - l] % MOD + MOD) % MOD;
    };
    B[0] = 1;
    for (int i = 1; i < N; i++) {
        B[i] = B[i - 1] * BASE % MOD;
    }
    int n;
    cin >> n;
    vector<string> s(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    ull sz = 0;
    for (char i : s[0]) {
        H[sz + 1] = (H[sz] * BASE % MOD + i) % MOD;
        sz++;
    }
    string ans = s[0];
    for (int i = 1; i < n; i++) {
        ull ssz = s[i].size();
        ull com = 0, len = min(sz, ssz), sh = 0;
        for (ll j = 1; j <= len; j++) {
            sh = (sh * BASE % MOD + s[i][j - 1]) % MOD;
            if (sh == hash(sz - j, sz))
                com = j;
        }
        // cout << sz << " " << com << endl;
        sz -= com;
        while (com) {
            ans.pop_back();
            com--;
        }
        for (char j : s[i]) {
            ans.push_back(j);
            H[sz + 1] = (H[sz] * BASE % MOD + j) % MOD;
            sz++;
        }
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}