给出一个串，每次只能在首端或尾端加入字符，问至少要加入多少个字符，才能使得这个串为循环串（由出现次数大于等于2的循环节构成）
100组数据 每组数据字符串长度不超过1e5
sol：
在头部加和在尾部加其实是一样的，设原始串的长度为len,则有
(s[0..fail[len-1]]=s[(len-1-fail[len-1])..len-1])
若s本身已经是循环串了，用字母a表示一个循环节，那么s可以表示为aaaaa...aaaaa
那么根据fail数组的定义，len-1-fail[len-1]将会等于最小循环节的长度。可以用这个值能否整除len判断原串是否是循环串，即len%(len-1-fail[len-1])=0是s为循环串的充要条件。
必要性显然，充分性证明如下：
考虑反证法
若s本身不是循环串，那么s可以看作是最小循环节重复x次加上其部分前缀构成的。
那么s可以表示为循环节的前缀+循环节的后缀+x-1次循环节+循环节的前缀
fail[len-1]+1为最后俩部分的长度，k=len-1-fail[len-1]为循环节的长度。
那么k*x-fail[len-1]-1为要补的长度
那么对于这题，当s为循环串时输出0即可。否则，补齐第二个前缀剩下的部分，也就是循环节的剩余部分即可。
注意第四第五部分的长度可能为0，此时答案为len。
// Problem: Cyclic Nacklace
// Contest: Virtual Judge - HDU
// URL: https://vjudge.net/problem/HDU-3746#author=0
// Memory Limit: 32 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
#define ll long long
int rd() {
int s = 0, f = 1; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') {s = s * 10 + c - '0'; c = getchar();}
return s * f;
}
int len;
char s[maxn];
int fail[maxn];
void getfail() {
int match = -1;
fail[0] = -1;
for (int i = 1; i < len; i++) {
while (match >= 0 && s[match+1] != s[i]) {
match = fail[match];
}
if (s[match+1] == s[i]) {
match++;
}
fail[i] = match;
}
//for (int i = 0; i < len; i++) printf("fail[%d]==[%d]
", i, fail[i]);
}
int main() {
int T = rd();
while (T--) {
scanf("%s", s);
len = strlen(s);
//for (int i = 0; i < len; i++) fail[i] = -1;
getfail();
int k = len - fail[len-1] - 1;
//printf("k == %d len == %d fail[k-1] == %d fail[len - 1] == %d
", k, len, fail[k-1], fail[len-1]);
if (len % k == 0 && len != k) {
puts("0");
} else printf("%d
", len/k*k-fail[len-1]-1);
}
}