Visits: 108

计蒜客 – 重复的密文

蒜头君收到了一串密文，但是由于接收器坏了，他不停的重复接收，终于，蒜头君把插头拔了，机器停止了，但是蒜头君已经收到了一个很长字符串，它是由某个原始串不停的重复形成了，因为断电，最后一遍也不一定是完整的。蒜头君现在想知道这个原始串的最短可能长度是多少。

输入格式

第一行输入一个正整数 $L(1 < L \leq 10^6)$，表示这个字符串的长度。

第二行输入一个字符串，全部由小写字母组成。

8
cabcabca

输出格式

答案输出，输出最短的可能长度。

3

这道题是求 KMP 的最小循环节。

仔细观察 next[] 数组，可以发现，如果出现循环，那么除了第一个循环节的值都是 $0$，从第二个循环节开始，包括最后一个，都是递增的，而且记录了最长公共前缀。

所以利用 KMP 求出 next[] 数组，L - next[L] 就是答案。

注：next[] 数组也常被称作 fail[] 数组，失败链接值。

#include <bits/stdc++.h>

// 为了编程方便，next 数组下标从 1 开始，所以 string 也要下标从 1 开始，所以封装了一个 read
char* read(int length) {
    char* s = (char*)malloc(sizeof(char) * (length + 2));
    for (int i = 1; i <= length; i++) {
        char c;
        scanf("%c", &c);
        s[i] = c;
    }
    s[length + 1] = '\0';
    return s;
}

// 以字符串 t 求 next 数组，n 为字符串长度
int* getNext(const char* t, int length) {
    int* next = (int*)malloc(sizeof(int) * (length + 1));
    next[1] = 0;
    for(int i = 2; i <= length; i++) {
        int j = next[i - 1];
        while(t[j + 1] != t[i] && j > 0) {
            j = next[j];
        }
        if(t[j + 1] == t[i]) {
            next[i] = j + 1;
        } else {
            next[i] = 0;
        }
    }
    return next;
}

void print(const char * t, const int* next, int n) {
    for (int i = 1; i <= n; i++) {
        printf("%c%c", t[i], i == n ? '\n' : '\t');
    }
    for (int i = 1; i <= n; i++) {
        printf("%d%c", next[i], i == n ? '\n' : '\t');
    }
}

int main() {
    int n;
    scanf("%d\n", &n);
    char* t = read(n);
    int* next = getNext(t, n);
//    print(t, next, n);
    printf("%d\n", n - next[n]);
}