题目链接：Codeforces 1200E
维护一个字符串\(r\)表示答案，然后对于每一个字符串\(s_i\)，和相同长度的\(r\)的后缀\(r_{s}\)拼接起来（\(s_i\)在前，\(r_s\)在后），求\(\rm fail\)函数，得到最长公共前后缀的长度，取当前字符串的长度取一个最小值，这个值就是\(s_i\)添加到\(r\)中之前要删除的前缀的长度。
渐进时间复杂度\(O(n)\)。
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 <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = int(1E5) + 5;
const int MAX_L = int(1E6) + 5;
int n;
string str[MAX_N];
string ans;
int fail[MAX_L];
char s[MAX_L];
int cal(const string &u, const string &v) {
int tot = 0;
for (auto const &c: u) s[++tot] = c; s[++tot] = '#';
for (auto const &c: v) s[++tot] = c; s[tot + 1] = '!';
for (int i = 2, j = 0; i <= tot; ++i) {
while (j && s[i] != s[j + 1]) j = fail[j];
if (s[i] == s[j + 1]) ++j;
fail[i] = j;
}
return min(fail[tot], int(u.size()));
}
int main() {
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> str[i];
ans = str[1];
for (int i = 2; i <= n; ++i) {
string suf = ans.substr(max(int(ans.size() - str[i].size()), 0), str[i].size());
int cut = cal(str[i], suf);
ans += str[i].substr(cut, str[i].size() - cut);
}
cout << ans << endl;
return 0;
}
|