CF319D 题解

FutureSnow · 2022-10-02 15:37:25 · 题解

想办法暴力水过去。

首先考虑对每个子串都做一遍匹配。我们从小到大枚举子串的长度，然后通过枚举起点，来暴力地判是否是重复段。如果找到了就直接替换掉，并且重新从长度为 1 的子串开始枚举。

这种算法看起来时间复杂度是 O(n^3) 的，但感性分析一下就会发现，常数非常的小，甚至接近 \frac{1}{n}。因为当重复段较小时，枚举的长度就会很快归零并重新枚举。当重复段较大时，每一次删去字符串的长度较长，也降低了时间复杂度。

另外，建议使用 char 数组存储字符串，进一步降低常数。

#include <bits/stdc++.h>
#define Maxn 50050
using namespace std;

char str[Maxn], s[Maxn];

int main (){
    cin >> str;
    int len = strlen(str);
    for(int i = 1; i <= len; i++){
        s[i] = str[i - 1];
    }
    int n = len;
    for(register int i = 1; i <= n / 2; i++){//i是枚举长度
        int tot = 0;
        for(register int j = 1; j <= n - i; j++){
            if(s[j] == s[j + i]){
                tot++;
            }   
            else{
                tot = 0;
            }
            if(tot == i){
                for(register int k = j + 1; k <= n - i; k++){
                    s[k] = s[k + i];
                }
                n -= i;
                i = 0;
                break;
            }
        }
    }   
    s[n + 1] = 0;
    cout << s + 1 << endl;

    return 0;
}