CF319D Have You Ever Heard About the Word? 题解

狂风之息 · 2021-11-27 21:33:58 · 题解

暴力真的可以水过这题（

思路

首先令 n 表示 X 的长度

根据题意，我们知道：

要求的 XX 先要求 短 再要求 靠左 。

所以我们可以从小到大枚举 X 的长度 len (1 \le len \le n/2)，再从左到右把重复的部分去掉即可。

那么怎么去掉重复的部分呢？

看看题目：n\le50000，题目时限 6 s, 其实可以 O(n) 暴力匹配，卡卡常就过了。

至于怎么暴力匹配，我是用了两个指针 p1 和 p2 ，每次比较它们对应的字符，用 cnt 存储已经有连续多少个相同的字符。当 cnt=len 时就将两个指针之间的部分删除。

删除部分再用链表优化一下就行了。

时间复杂度 O(n^2/2) (这个除2必不可少)

最慢的点 4.03 s。

code:

#include<bits/stdc++.h>
using namespace std;
char s[50005];
int nxt[50005];
int main(){
    scanf("%s",s+1);
    int n=strlen(s+1);
    for (int i=1;i<n;i++)
        nxt[i]=i+1;
    int len=1;
    while (len*2<=n){ //枚举长度然后暴力缩短
        int p1=1,p2=1;
        for (int i=1;i<=len;i++) //放好指针
            p2=nxt[p2];
        int cnt=0,lst=1;
        while (p2){
            if (s[p1]==s[p2])
                cnt++;
            else {cnt=0;lst=nxt[p1];}
            if (cnt==len){ //如果已经有连续len个匹配的就删掉
                nxt[p1]=nxt[p2];
                p1=lst;p2=nxt[p2];
                cnt=0;
            }else{
                p1=nxt[p1];
                p2=nxt[p2];
            }
        }
        len++;
    }
    int p=1;
    while (p){
        printf("%c",s[p]);
        p=nxt[p];
    }
    return 0;
}