最小重复子串

sky分析

“轰”一声巨响，惊醒了沉睡中的Floyd Warshall市

sxy在中心大楼，透过24k黄金玻璃窗，凝视着一片惨白的西方，巨响就是从那里传来的

"报告！---"

"嗯？什么事？“ sxy放下手中的一沓资料，向面前的黑衣人询问道

"报告首领，我们已经成功截获到那边传来的非正常的，正弦波信号！"

"什么，正弦波信号！！”sxy飞身而起，“看来错不了了，果然是那东西，错乱的线性空间内泄露来的正弦波信号，那就是通往线性世界的时空隧道，竟然跑到OI的世界里来了！把截获到的信号发给我！"

”是！“黑衣人转身离去

不久，信号就被送到sxy的办公桌上

嗯，我们需要对截获到的信号进行傅里叶分析，以期望能够得到时空隧道那边的信息。但为了便于分析，我们最好先找到信号重复最小单位，因为信号就是以这样的最小单位为单位地重复，因此我们只需要分析这一段信号的最小重复单位，就能知道这段信号表达的意思了(因为整个信号都是按这个单位重复的)。于是sxy找到了你，他相信你一定能解决这个问题的。

输入格式

第一行，一个整数N，表示截获到的信号的长度

第二行一个长度为N的字符串，表示这个信号

输出格式

这个信号的最小重复单位的长度

样例

样例输入1

6
233233

样例输出1

3

样例输入2

8
12312341

样例输出2

8

解释

233233这个字符串的最小重复单位为233，其长度为3

12312341这个字符串最小重复单位是他自己，长度为8

数据范围与提示

1 <= N <= 1000

经典水题，你开心就好

解题思路：结合希尔排序思想进行步长求解法，上代码

如果字符重复的话，那么i , i + gap, i + gap + gap 都是相同的

#include<iostream>
#include<string>
using namespace std;
int main() {
    int N;
    cin>>N;
    string s;
    cin>>s;
    for (int i = 1; i <= N; i++) {
        if (N % i == 0) {
            int m = 0;
            for (int k = i; k < N; k++) {
                if (s[k] != s[k - i]) {
                    m = 1;
                    break;
                }
            }
            if (m == 0) {
                cout<<i;
                break;
            }
        }
    }
    return 0;
}

希尔排序代码：

//交换法
void shellSort_two(int v[], int length) {
    int temp = 0;
    int count = 0;
    for (int gap = length / 2; gap > 0; gap /= 2) {
        //之所以 i = gap 是因为数组从下标为0开始，视频中给的是gap + 1是因为下标从1开始
        for (int i = gap; i < length; i++) {
            for (int j = i - gap; j >= 0; j -= gap) {
                if (v[j] > v[j + gap]) {
                    temp = v[j];
                    v[j] = v[j + gap];
                    v[j + gap] = temp;
                }
            }
        }
    }
    for (int i = 0; i < 5; i++) {
        cout<<v[i]<<" ";
    }
}

最小重复子串

原文：https://www.cnblogs.com/mrmrwjk/p/14638760.html