一、题目
1、原题链接
141. 周期
2、题目描述
一个字符串的前缀是从第一个字符开始的连续若干个字符，例如 abaab 共有 5 个前缀，分别是 a，ab，aba，abaa，abaab。
我们希望知道一个 N 位字符串 S 的前缀是否具有循环节。
换言之，对于每一个从头开始的长度为 i（i>1）的前缀，是否由重复出现的子串 A 组成，即 AAA…A （A 重复出现 K 次,K>1）。
如果存在，请找出最短的循环节对应的 K 值（也就是这个前缀串的所有可能重复节中，最大的 K 值）。
输入格式
输入包括多组测试数据，每组测试数据包括两行。
第一行输入字符串 S 的长度 N。
第二行输入字符串 S。
输入数据以只包括一个 0 的行作为结尾。
输出格式
对于每组测试数据，第一行输出 Test case # 和测试数据的编号。
接下来的每一行，输出具有循环节的前缀的长度 i 和其对应 K，中间用一个空格隔开。
前缀长度需要升序排列。
在每组测试数据的最后输出一个空行。
数据范围
2≤N≤1000000
输入样例：
3
aaa
4
abcd
12
aabaabaabaab
输出样例：
Test case #1
2 2
3 3
Test case #2
Test case #3
2 2
6 2
9 3
12 4
二、解题报告
1、思路分析
思路来源：y总讲解视频
y总yyds
数据范围为106，时间复杂度需控制在O(n)
（1）由KMP算法可知，next[i]的含义：长度为i的字符串中最长相等前后缀的长度。
（2）对于任意子串i-ne[i]是最小的循环节，而大于i-ne[i]的循环节的长度必然是i-ne[i]长度的倍数。
（3）若对于某个子串i-ne[i]可以整除i，则说明最小循环节在该子串中出现了整数次，满足题目要求，否则不满足。
（4）模拟上述过程，输出结果即可。
2、时间复杂度
时间复杂度为O(n)
3、代码详解
#include <iostream>
using namespace std;
const int N=1000010;
char s[N];
int ne[N];
int n;
int main(){
int num=1;
while(cin>>n){
if(!n) break; //输入0，结束循环
cin>>s+1;
//求next数组
for(int i=2,j=0;i<=n;i++){
while(j&&s[i]!=s[j+1]) j=ne[j];
if(s[i]==s[j+1]) j++;
ne[i]=j;
}
cout<<"Test case #"<<num++<<endl;
for(int i=1;i<=n;i++){
int t=i-ne[i]; //t记录最最小循环节的长度
int k=i/t; //k记录最小循环节出现的次数
if(i%t==0&&k>1){ //如果最小循环节在该子串中出现了整数次，而且出现的次数大于1，输出子串长度和最小循环节出现次数
cout<<i<<' '<<k<<endl;
}
}
cout<<endl;
}
return 0;
}
三、知识风暴
KMP算法
KMP算法主要解决字符串的匹配问题。
KMP主要思想：在匹配过程中，每当匹配过程中出现字符不相同的情况，不从头开始重新匹配，而是回退到已经部分匹配的位置后继续重新匹配，而退回的位置是由next数组来决定（next[i]表示长度为i的字符串的最长相等前后缀的长度）。
