【题目来源】
https://oj.czos.cn/p/2360

【题目描述】
给定若干个长度≤10^6 的字符串，询问每个字符串最多是由多少个相同的子字符串重复连接而成的。
如：ababab 则最多有 3 个 ab 连接而成。

【输入格式】
输入若干行（所有行的字符串的长度之和≤10^7），每行有一个字符串，字符串仅含英语小写字母。特别的，字符串可能为 . ，即一个半角句号，此时输入结束。

【输出格式】
对于每行输入，输出一个整数，代表计算的结果。​​​​​​​

【输入样例】
abcd
aaaa
ababab
.​​​​​​​

【输出样例】
1
4
3

【数据范围】
字符串长度≤10^6，
所有行的字符串的长度之和≤10^7。

【算法分析】
● 循环节：https://blog.csdn.net/hnjzsyjyj/article/details/146168602

● 理解 KMP 算法中 next 数组涵义所需的几个概念
（1）非平凡前缀，指除了最后一个字符以外，一个字符串的全部头部组合。简称前缀。
（2）非平凡后缀，指除了第一个字符以外，一个字符串的全部尾部组合。简称后缀。
（3）最长公共前后缀，指一个字符串的最长且相等的前缀与后缀。例如，字符串 ABCxyzABC 的最长公共前后缀为 ABC。

● next 数组的涵义：next[i] 表示字符串前 i 个字符的最长公共前后缀长度。
例如，字符串 "ABABA" 的前 3 个字符 "ABA" 的最长公共前后缀为 "A"，长度为 1；前 5 个字符 "ABABA" 的最长公共前后缀为 "ABC"，长度为 3。
这可由字符串 "ABABA" 的 next 数组（字符串下标从 1 开始）进行验证。例如，next[3]=1，next[5]=3。

● 假设字符串 ‌s[1 ... i]‌ 由 ‌k‌ 个循环节 ‌P 构成，总长度 ‌i=kL‌。其中，L 为循环节长度。
由 next 数组的涵义知，next[i]‌ 等于 ‌k-1‌ 个循环节的总长度，即 ‌next[i]=(k-1)L‌。
由 ‌i=kL‌ 和 ‌next[i]=(k-1)L‌ 联立得：‌L=i-next[i]‌‌

● 当 i%(i-next[i])==0 时，存在循环节。
循环节长度 L=i-next[i]，循环次数 K=i/L=i/(i-next[i])。
例如，aabaabaabaab 的 next 数组如下表所示（字符串下标从 1 开始）。

若 i=12 且 next[i]=9，则循环节长度 L=i-next[i]=12-9=3，循环次数 K=i/L=i/(i-next[i])=12/3=4，表示该前缀（或称子串）由长度为 3 的循环节重复 4 次构成‌。
​​​​​​​
【算法代码】

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

const int N=1e6+5;
int ne[N];

void getNext(string t) {
    int len=t.length();
    int i=0,j=-1;
    ne[0]=-1;
    while(i<len) {
        if(j==-1 || t[i]==t[j]) {
            i++,j++;
            ne[i]=j;
        } else j=ne[j];
    }
}

int main() {
    string t;
    while(cin>>t) {
        if(t==".") break;
        int len=t.size();
        getNext(t);

        int L=len-ne[len];
        if(len%L==0) cout<<len/L<<endl;
        else cout<<1<<endl;
    }
    return 0;
}

/*
in:
abcd
aaaa
ababab
.

out:
1
4
3
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/160215718
https://blog.csdn.net/hnjzsyjyj/article/details/160224665
https://blog.csdn.net/hnjzsyjyj/article/details/146154773
https://blog.csdn.net/hnjzsyjyj/article/details/146168602