题解 CF1200E 【Compress Words】

这题事实上要我们求的是:

当前拼接好的串的后缀和待拼接串的前缀的最大匹配长度。

可能有点绕，我们结合样例2来理解下。

当前拼接好的串 $sample$

待拼接串 $please$

后缀和前缀的最大匹配 $ple$

最大匹配长度 $3$

所以我们只要把 $ase$ 加入到当前拼接好的串。

此时当前拼接好的串 $samplease$

~~这下应该理解了吧~~

那么怎么求最大匹配长度呢？

匹配？想到啥？ KMP!

和待拼接串的前缀匹配？

那么构造一个待拼接串在前,当前拼接好的串在后的新串，求出当前拼接好的串的最后一个字符的 $kmp[i]$ 值不就行了？(啥是[ $kmp[i]$ ](https://www.luogu.org/problem/P3375)?)

值得注意的是最大匹配长度不会超过待拼接串的长度，所以每次只要截取当前拼接好的串的一部分串就行了

(其实这个相同也可以用hash判。不过据我所知许多比较弱的hash都已经被hack了，作为cf题建议采用稳妥些的做法，免得赛后fst...)

理解的话代码实现并不困难:

/*
    Author:Frozencode
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll maxn = 1000010;
const ll INF = 2147483647;
ll n,len,anslen,top,minn,kmp[maxn];
char c[maxn],ans[maxn];
int main()
{ 
    cin>>n;
    for(int i = 1;i <= n;i++){
        scanf("%s",c + 1);
        len = strlen(c + 1);
        minn = min(anslen,len);//截取长度。
        top = len;
        c[++top] = '#';//加个奇怪字符防止最大匹配长度超过待拼接串的长度。
        kmp[0] = 0;
        kmp[1] = 0;
        for(int j = 1;j <= minn;j++)c[++top] = ans[anslen - (minn - j)];//拼接。
        for(int j = 1;j < top;j++){
            ll k = kmp[j];
            while(k && c[k + 1] != c[j + 1])k = kmp[k];
            if(c[k + 1] == c[j + 1])k++;
            kmp[j + 1] = k;
        }//求kmp数组的值,这里不理解的话可以点上面的链接进去看看。
        for(int j = kmp[top] + 1;j <= len;j++)ans[++anslen] = c[j];//更新当前拼接好的串。
    }
    for(int i = 1;i <= anslen;i++)cout<<ans[i];
    return 0;
}