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;
ull H[N], B[N];
void sol() { auto hash = [&](int l, int r) { 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; } 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; }
|