HDU 3746 Cyclic Nacklace(KMP求循环节)

#include <bits/stdc++.h>
#define maxn 100005
#define ll long long
using namespace std;
int T;
char s[maxn];
int Next[maxn];

void init(){
	int j = 0, k = -1;
	int len = strlen(s);
	memset(Next, -1, sizeof(Next));
	while(j < len){
		if(k == -1 || s[j] == s[k]){
				k ++;
				j ++;
				Next[j] = k;
		}
		else k = Next[k];
	}
}

int main()
{
	scanf("%d", &T);
	while(T--){
		scanf("%s", s);
		init();
		int len = strlen(s);
		if(Next[len] == 0) {
			printf("%d\n", len);
			continue;
		}
		if(len % (len - Next[len]) == 0){
			puts("0");
		}
		else{
			int xx = len - Next[len];
			printf("%d\n", xx - len % xx);
		}
	}
	return 0;
}