题目描述 给定一个字符串S求该字符串的最小循环节长度及最小循环节。 输入 多组输入数据，每组数据输入一个字符串，直到文件结束。 输出 输出一个整数代表这个字符串的最小循环节的长度，输出一串字符串代表最短循环节，中间用空格隔开。
样例输入 aaa 样例输出 1 a 提示 题目数据:长度小于1e6.
原题链接：最小循环节
首先得知道什么是最小循环节 kmp的next数组里存的是i之前的串的前缀和后缀匹配的最大长度，next[strlen(s)]就代表的是整个s串的前缀和后缀的最长匹配长度，用总长度减去这个值就是s串的最小循环节。 最小循环节的定义是一个串可以由某个串循环得到，不一定是整数次循环， 比如abca的最小循环节是abc
代码：
#include<iostream> #include<string> #include<algorithm> using namespace std; const int maxn=1000010; string str; int nxt[maxn]; void get_next() { int len=str.length(); for(int q=0,i=1;i<len;++i) { while(q&&str[q]!=str[i]) q=nxt[q]; if(str[q]==str[i]) ++q; nxt[i+1]=q; } } void solve() { int len=str.length(); int tot=0; string s; tot=len-nxt[len]; s=str.substr(0,tot); cout<<tot<<" "<<s<<endl; } int main() { while(cin>>str) { get_next(); solve(); } return 0; }参考博客： 呓语
