Period POJ - 1961（kmp,最小循环节）

题意：给定一个字符串，ascii码在97到126之间（字母）如果前i个字符组成的字符串是由子字符串循环一定次数组成的，则该字符串为周期串，子字符串为循环节。 比如aabaabaabaab，在前两个字符中a出现了两次，循环节为a。在前6个字符中，循环节出现了2次，循环节为aab，在前9个字符中，循环节出现了3次，循环节为aab；在12个字符中循环节出现了4次，循环节为aab。请编程写出给定字符串的n长度的周期串以及循环节出现的次数

AC代码：

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <algorithm>
#define ing long long
using namespace std;
const int maxn=1e6+5;
int nxt[maxn];
string s;
void getnext() {
  int k=-1,i=0;
  nxt[0]=-1;
  while(i<s.size()) {
    if(k==-1||s[i]==s[k])nxt[++i]=++k;
    else k=nxt[k];
  }
}
int main() {
  int n,kase=1;
  while(cin>>n&&n) {
    memset(nxt,0,sizeof(nxt));
    cin>>s;
    //printf("Test case #%d\n",kase++);
    printf("Test case #%d\n",kase++);
    getnext();
    for(int i=0; i<s.size(); i++) {
      int k=i+1;
      if(k%(k-nxt[k])==0&&k/(k-nxt[k])!=1)
        cout<<k<<" "<<k/(k-nxt[k])<<endl;
    }
    cout<<endl;//注意格式 
  }
}