题意
给出\(n\)个字符串, 将字符串按顺序拼接. 拼接时删除后面字符串的前缀与前面字符串的后缀中的最长相同部分.
例如sample与please拼接成为samplease
\(1 \leq n \leq 10^5\), \(\sum|s_i| \leq 10^6\)
题解
设将\(u\)和\(v\)拼接在一起, 用KMP求出\(s = v|u\)(|是任意分隔符)的失配数组\(next[]\).由于失配数组代表前后缀的最长长度, \(next[|s|]\)即为\(v\)的前缀与\(u\)的后缀相同部分的最长长度.
注意到这个最长长度不会超过\(|v|\), 因此我们只需把\(u\)的最后\(|v|\)个字符接到分隔符后. 时间复杂度\(O(\sum|s_i|)\)
赛时十分傻逼地忘了用分隔符把\(u,v\)分隔开, 疯狂WA到怀疑人生...顺便吐槽一句这个数据真的弱
代码
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
int Next[4000010];
void getFail(string & P){
for(int i = 0;i <= (int)P.size();i++)Next[i] = 0;
int p_size = P.size();
Next[0] = Next[1] = 0;
for(int i = 1;i < p_size;i++){
int j = Next[i];
while(j and P[i] != P[j])j = Next[j];
Next[i+1] = (P[j] == P[i]?j+1:0);
}
}
string process(string & u,string & v){
string x = v;
x += '|';
for(int i = max(0,(int)(u.size() - v.size()));i < (int)u.size();i++)x += u[i];
getFail(x);
string tans = "";
for(int i = Next[x.size()];i < (int)v.size();i++)tans += v[i];
return tans;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
string ans = "";
string u,v;
if(n == 1){
cin >> u;
cout << u;
return 0;
}
cin >> u >> v;
ans = u + process(u,v);
for(int i = 3;i <= n;i++){
cin >> v;
ans += process(ans,v);
}
cout << ans;
return 0;
}
|