【題解】Cyclic Nacklace HDU-3746⭐⭐⭐ 【KMP循環節問題】

Cyclic Nacklace HDU-3746
第一問題が来ました
文字列を送ります.この文字列の末尾に最低何文字を追加すれば、この文字列に繰り返しのシーケンスが得られますか?
Input
最初の行は整数T(0後のT行の1行に1文字列、小文字からなり、文字列の長さは3<=L==100000.
Output
データのセットごとに結果を出力します.
Examples
Sample Input 3 ppp pip Machinel earning Sample Output 0 1 15
ベント
件名:
クイズ:
KMPアルゴリズムについての理解は、単にテンプレートをセットするだけではなく、その真髄-next配列next配列の意味を理解するには、T[0...i-1]における最大の共通プレフィックス/サフィックス、0-indexedに対して求められるnext配列は、実際には1-Mである.
next[M]はTの中の最大の公共の本当のプレフィックス/後綴りで、このようにM-next[M]は循環節の長さlenであるべきです.もしnext[M]が0ならば、循環節がないと説明します.M%len==0は循環節が完全に重複して含まれています.
経験小結:

#include
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const int inf = 1 << 30;
const int maxn = 1e5+10;

char T[maxn];
int nxt[maxn], M;
void getNext(){
    ms(nxt, 0);
    int i = 0, j = -1;
    nxt[0] = -1;
    while(i < M){
        if(j == -1 || T[i] == T[j])
            nxt[++i] = ++j;
        else j = nxt[j];
    }
}
int main() {
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%s",T);
        M = strlen(T);
        getNext();
        int len = M-nxt[M]; //      
        if(nxt[M] == 0)     //      
            cout << M << endl;
        else if(M%len == 0) //       
            cout << 0 << endl;
        else                //     -     
            cout << len-M%len << endl;
    }

    return 0;
}