循环节问题

经典的利用kmp算法解决。
n-net[n]就是最小循环节cyc。
如果n%cyc==0那么我们可以说正好,不用加
否则就得加后缀
但是有一个需要判断的地方,当cyc==n的时候
没有循环节,那么我们要特殊判断了

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int max_n = 1e5+100;
int net[max_n];
void getnext(char p[],int size) {
    int i = 0;int j = -1;
    net[0] = -1;net[size]=500;//绝对不会出现的数
    while (i < size) {
        if (j == -1 || p[i] == p[j]) {
            ++i;++j;
            if (p[i] != p[j])
                net[i] = j;
            else net[i] = net[j];
        }
        else j = net[j];
    }
}
char p[max_n];
int main(){
    int T;scanf("%d",&T);
    while (T--){
        scanf("%s",p);
        int n=strlen(p);
        getnext(p,n);
        int cyc = n-net[n];
        if (cyc==n)printf("%d\n",n);
        else if (n%cyc==0)printf("0\n");
        else printf("%d\n",cyc-n%cyc);
    }
}