Compress Words
本人蒟蒻,请看更详细的题解
CF1200E Compress Words 题解
重点是利用KMP计算最长前后缀,注意几个点:长度、越界。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int ne[N];
void kmp(string ss) {
int n = ss.length();
ss = ' ' + ss;
ne[0] = ne[1] = 0;
for (int i = 2,j=0; i <= n; i++) {
while (j && ss[i] != ss[j + 1]) j = ne[j];
if (ss[i] == ss[j + 1]) j++;
ne[i] = j;
}
}
int main() {
int n;
cin >> n;
string ans, s;
cin >> ans;
n--;
while (n--) {
cin >> s;
int len = min(s.length(), ans.length());
string ss = s + "#$" + ans.substr(ans.length()-len,len);
kmp(ss);
for (int i = ne[ss.length()]; i < s.length(); i++) ans+=s[i];
}
cout << ans;
return 0;
}