Power Strings

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;
        }
    }
}