题解 CF1200E 【Compress Words】

题意简述

• 给定 \(n\) 个单词，将这 \(n\) 个单词从前往后拼接在一起，若相邻两个单词的后缀和前缀相同则将其重合在一起。

• 如输入 sample please ease in out，sample 与 please 拼接得 samplease，samplease 与 ease 拼接仍得 samplease，最终得 sampleaseinout

题目分析

题目的关键在于求出两个字符串之间的最长公共部分，即相等的前缀与后缀。这很容易让人联想到 KMP 的 \(next\) 数组，它的定义是一个字符串的前缀的最长的相同的前缀与后缀的长度，\(next[len - 1]\) 的定义就是这个字符串的最长的相同的前缀与后缀的长度。

因此，对于字符串 \(s1\) 和 \(s2\)，我们只需要将 \(s2\) 拼接在 \(s1\) 前面，例如将 sample 与 please 拼接为 pleasesample，再求出这个字符串的 \(next[len - 1]\) 等于 \(2\)，就可以简单地得到公共部分为 ple，再从 \(2\) 开始截取 please 的后半部分 ease 拼接到 sample 后面即可。

对于 \(n\) 个字符串，则应该按照上面的方法依次拼接。

P.S. 一个优化：因为两个字符串之间的最长公共部分的长度显然不可能大于其中任意一个字符串的长度，所以在一开始拼接时，只需要求出两个字符串中较短的的长度 \(l\)，将第一个字符串的后 \(l\) 个字符拼接到第二个字符串后面，再求 \(next[len - 1]\) 的值。

同时，为了防止求next时将另一个字符串也算进来，导致“共同部分”跨过两个字符串之间，要在中间插入一段数据中几乎不可能出现的字符串。因为如果某个真子串在字符串中只出现一次，最长的相同前后缀就不可能包括这个字串，也就杜绝了求出的长度越过两个字符之间的可能性。

代码

#include
using namespace std;

const int MAXN = 1000000 + 500;

int nxt[MAXN];

int getNext(string s2) {
	nxt[0] = -1;
	int i = 0, j = -1;
	int len2 = s2.size();
	while(i < len2) {
		if(j == -1 || s2[i] == s2[j]) {
			i++;
			j++;
			nxt[i] = j;
		} else {
			j = nxt[j];
		}
	}
	return j;
}

int main() {
	string s, ans;
	int n, len;
	
	cin >> n >> s;
	ans = s;
	for(int i = 2; i <= n; i++) {
		cin >> s;
		len = min(ans.size(), s.size()); //显然，共同部分的长度不会超过两个字符串中的任何一个
        //为了防止求next时将另一个字符串也算进来，导致“共同部分”跨过两个字符串之间，要在中间插入一段数据中几乎不可能出现的字符串
		string tmp = s + "Idealistoj neniam maljuni?as." + ans.substr(ans.size() - len);
		int res = getNext(tmp); //求出相同的最长前缀和后缀，即两个字符串的公共部分的长度
		ans += s.substr(res); //0 ~ res-1 的部分都是与s的公共部分，只要将res之后的部分接到ans后面既可以了
	}
	
	cout << ans << endl;
	
	return 0;
}