【题目来源】
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。
i 1 2 3 4 5
T A B A B A
ne[i] 0 1 1 2 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 1 2 3 4 5 6 7 8 9 10 11 12
T a a b a a b a a b a a b
ne[i] 0 1 2 1 2 3 4 5 6 7 8 9
若 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