@description@
给你一个长度为 n 的由小写字母组成的字符串，让你在末尾增加尽量少的字母，使它变为循环串。
input
多组数据。第一行数据组数 T，T <= 100。
接下来 T 行，每行一个长度为 n 的字符串，n <= 100000。
output
对于每组数据，输出最少的字母数。
sample input
3
aaa
abca
abcde
sample output
0
2
5
@solution@
【我只是来复习 KMP 的……】
update in 2019/11/12 : 本题可以直接用 border 与周期的转化，以及弱周期引理搞定————来自某正在复习的博主（如果你不知道前面的是什么东西，还是看下面的分析吧）。
如果长度为 n 的串 (S) 是一个循环节为 (k) 的循环串的前缀，那么我们可以将它补成循环节为 (k) 的循环串。
如果 (S) 是循环节为 (k_1) 与循环节为 (k_2) 两个串的前缀，则 (S) 一定是循环节为 (gcd(k_1, k_2)) 串的前缀。
假如 (k_1) 是 (k_2) 的倍数，则将 (S) 补成循环节为 (k_2) 的代价一定小于等于改成循环节为 (k_1) 的。
综合以上性质，我们相当于是要求解以 (S) 为前缀的循环串的最小循环节。
然后可以证明，"(S) 是一个循环节为 (k) 的循环串的前缀" 与 "(S) 长度为 (n-k) 的后缀等于 (S) 长度为 (n-k) 的前缀" 等价，即它们互为充要条件。
所以我们就可以用 KMP 搞了。
注意两种特殊情况：（1）(S) 本身是循环串（2）以 (S) 为前缀的循环串的最小循环节为 (S) 的长度。
@code@
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 100000;
void GetFail(char *T, int *f) {
int lenT = strlen(T);
f[0] = -1, f[1] = 0;
for(int i=2;i<=lenT;i++) {
int j = f[i-1];
while( j != -1 && T[j] != T[i-1] )
j = f[j];
f[i] = j + 1;
}
}
char S[MAXN + 5];
int fail[MAXN + 5];
void solve() {
scanf("%s", S); GetFail(S, fail);
int lenS = strlen(S);
if( fail[lenS] == 0 ) printf("%d
", lenS);
else if( lenS % (lenS - fail[lenS]) == 0 ) printf("%d
", 0);
else printf("%d
", (lenS - fail[lenS]) - lenS%(lenS - fail[lenS]));
}
int main() {
int T; scanf("%d", &T);
for(int i=1;i<=T;i++) solve();
}
@details@
一开始写得极其复杂……还讨论了它最后循环串的循环节等各种稀奇古怪的东西……
几个月不碰这个玩意儿基本快忘完了吧……