Cyclic Nacklace HDU - 3746 （kmp最小循环节）

题意：现在给你一个字符串，请问在该字符串末尾最少添加多少个字符，可以让这个字符串获得重复循环序列。

AC代码：

#include <iostream>
#include <cstring>
using namespace std;
const int maxn=1e6+5;
int nxt[maxn],len;
string p;
void getnext(){
  int i=0,k=-1;
  nxt[0]=-1;
  while(i<len){
    if(k==-1||p[i]==p[k]){
      i++;
      k++;
      nxt[i]=k;
    }
    else k=nxt[k];
  }
}
int main(){
  ios::sync_with_stdio(false);
  int t;
  cin>>t;
  while(t--){
    cin>>p;
    len=p.size();
    getnext();
    int cir=len-nxt[len];
    if(cir==len)cout<<len<<endl;
      else  if(len%cir==0)cout<<0<<endl;
    else cout<<cir-(len%cir)<<endl;
  }
}