KMP!!!!骗子!!!!!骗子!!!!骗子!!!!!!

这道题被放进后缀数组题单里面。但是用后缀数组的方***超时。t到死。。。。。。。。。骗子!
后缀数组思路:
我们要求最小的循环子串。利用后缀数组:
如果 a1 a2 a3 a4 a5 a6 a7 a8 a9 的最小循环子串长为3即以a1 a2 a3为循环的话。
我们就可以发现 a4为起始的后缀应该和a1为起始的后缀的最大公共前缀和为6.即为a4的长度!!!!
这里是必须使a4的长度的。
那么我们就可以求出高度数组,利用st表。枚举s长度的因数,利用st表枚举长度。
但这会t!!!

正确的思路为KMP。我们再回到上面的例子:
a1 a2 a3 a4 a5 a6 a7 a8 a9
KMP的next数组求得其实就是求最长的相同前缀和后缀。(其实我个人觉得有点dp的感觉)
那我们看上面的例子,不就是求a9处的最大相同前缀后缀吗!!
a9求出的最大相同前缀后缀的长度为6.所以答案就是9/(9-6)=3
如果,最大相同前缀后缀长度被总长度减后不满足因数呢?
那么,答案就应该是1,没有循环子串。
因为首先一点,如果是因数的话一定有循环子串。
如果在有循环字串的基础上最长公共前后缀后还能更长,比如到a2。 而a1 a2 a3是循环字串
那么,我们可以断定a1==a2==a3==a4==.....a9 最小循环字串就变成a1了。矛盾。
所以,如果能整除就存在最小字串。如果不能,就不存在。为1

kmp代码如下:

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int max_n = 1e6 + 100;
char s[max_n];
int net[max_n];
void get_next(char* p,int n) {
    for (int i = 0, j = -1;i < n;) {
        if (j == -1 || p[i] == p[j])
            net[i++] = j++;
        else {
            if (j == 0)j = -1;
            else j = net[j - 1] + 1;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    while (cin >> s) {
        if (s[0] == '.')break;
        int n = strlen(s);
        get_next(s, n);
        if (net[n - 1] == -1)cout << 1 << endl;
        else {
            int len = n - 1 - net[n - 1];
            if (n % len == 0)cout << n / len << endl;
            else cout << 1 << endl;
        }
    }
}