题解 CF1200E Compress Words

· · 题解

1.题意简述

给定n个字符串，将其从左到右依次合并，并在合并时去重（去重的定义：找最大的i(i≥0),满足第一个单词的长度为i的后缀和第二个单词长度为i的前缀相等,然后把第二个单词第i位以后的部分接到第一个单词后面）。

2.题解

这是一道裸的KMP算法的题。前缀、后缀、最大相同的位置已经暴露了本题算法

既然已经确定了算法，那我们就来想一想以谁为模式串？由题意知，单词的总长度不超过1e6，（众所周知，OI中的不超过就是最大数据为1e6）如果我们以最终的答案串为模式串，那肯定会被T飞的。

这时候，就需要我们脑动优化时间复杂度，我们可以观察到最长匹配长度（题意简述中的i）<=min（答案串长度，新字符串长度）。那我们只需要将答案串中后min（答案串长度，新字符串长度）和新字符串中前min（答案串长度，新字符串长度）放在一起组成模式串，在对这个模式串进行一遍KMP即可。

每当我们得意之时，现实总会给我们当头一棒。因为以上算法过不了以下样例

答案串:ababa
新字符串:baba
合并后的模式串:ababababa
前缀:a,ab,aba,abab,ababa,ababab,abababa,abababab,ababababa
后缀:a,ba,aba,baba,ababa,bababa,abababa,babababa,ababababa

很明显，这时i=7，等等，这不是跨过了两个字符串了吗？不符合最长匹配长度（题意简述中的i）<=min（答案串长度，新字符串长度）。那我们是不是要从头在来了呢？也不是，三峡不是可以将江面分成两半吗，我们也可以在这两个字符串中间加一点东西隔开它们。题目保证了每个单词都是非空的，由大小写英文字母和数字组成，那只要加一些不是英文字母和数字的字符进去即可。

3.好了，讲了这么久，就上代码吧

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#define il inline
#define ll long long
#define gc getchar
#define R register
using namespace std;
//---------------------初始函数-------------------------------
//初始函数中都是一些优化，没有也没太大影响
il int read(){
    R int x=0;R bool f=0;R char ch=gc();
    while(!isdigit(ch)) {f|=ch=='-';ch=gc();}
    while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
    return f?-x:x;
}

il int max(int a,int b) {return a>b?a:b;}

il int min(int a,int b) {return a<b?a:b;}

//---------------------初始函数-------------------------------

const int MAXN=1e6+10;
int n,len,anslen,top,minlen;//len:新字符串的长度，anslen:答案串的长度，top:合并后模式串的长度，minlen:min（答案串长度，新字符串长度）
int kmp[MAXN];//用于匹配失配数组
char ans[MAXN],opt[MAXN];//ans:答案串,opt:新字符串

signed main(){//signed main==int main
    n=read();
    for(R int i=1;i<=n;++i){
        scanf("%s",opt+1);//将其整体往右移一位，方便之后的处理
        top=len=strlen(opt+1);
        minlen=min(anslen,len);
        opt[++top]='~';//将答案串和新字符串隔开
        for(R int j=1;j<=minlen;++j) opt[++top]=ans[anslen-(minlen-j)];//合并后的模式串
        //KMP算法求失配数组
        kmp[0]=0;kmp[1]=0;
        for(R int j=1;j<top;++j){
            int k=kmp[j];
            while(k&&opt[k+1]!=opt[j+1]) k=kmp[k];
            if(opt[j+1]==opt[k+1]) {++k;}
            kmp[j+1]=k;
        }
         //KMP算法求失配数组
        for(R int j=kmp[top]+1;j<=len;++j) ans[++anslen]=opt[j];
        //kmp[top]表示最长匹配长度，那kmp[top]+1到len就是答案串和新字符串不重合的部分，就将其加入到答案串中
    }
    for(R int i=1;i<=anslen;++i) printf("%c",ans[i]);
    return 0;
}