HDU 3746 Cyclic Nacklace (KMP求循环节问题)

<题目链接>

题目大意：

给你一个字符串，要求将字符串的全部字符最少循环2次需要添加的字符数。

【>>>kmp next函数 kmp的周期问题】 

解题分析:
KMP求循环节入门题。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+5;
char s[N];
int len,nxt[N];

inline void getnxt(){
  int j=0,k=-1;
  nxt[0]=-1;
  while(j<len){
    if(k==-1 || s[j]==s[k]) nxt[++j]=++k;
    else k=nxt[k];
  }
}
int main(){
  int T;cin>>T;while(T--){
    scanf("%s",s);
    len=strlen(s);
    getnxt();
    if(nxt[len]==0){          //不含循环多次的循环节,要循环两次，还需要添加自身
      printf("%d
",len);continue;      
    }
    int cir=len-nxt[len];         //计算出最小的循环节
    if(len%cir==0 && len/cir>1) puts("0");        
    else printf("%d
",cir-len%cir);
  }
}