首先要明白:如果一个串需要至少添加x(x>=0)个字符才能是有>=2个循环节的串,那么我可以只在串末尾添加,不需要去串头添加.(比如串cabc,循环节是abc,我可以在尾部添加ab即可.)

首先如果原始串已经有至少两个循环节就不必添加.当f[m]>0&&m%(m-f[m])==0时,不必添加.(结合之前的KMP循环节题目看看是不是这样.)

现在假设条件 f[m]>0&&m%(m-f[m])==0 不成立的时候呢?

重要结论:不论串S是不是循环的,如果想要S是一个循环串的话,那么它的最小循环节长度一定是len-f[len]. 其中len是串S的长度.

即不论S是不完整的循环串还是完整的循环串,len-f[len]一定是串S中去除末尾残缺部分之后,存在的最小循环节长度.现在来例证一下:

假设f[len]=0,那么是不是该串完全没有由部分子串构成最小循环节呢?是的.

只要一个串是上面的形式a或b,那么就不可能f[len]=0.

只要f[len]=0 (类似上面的形式c),那么它一定是单独成循环节,需要添加len个字符.

1 #include
2 #include
3 #include
4 using namespace std;
5 const int maxn=2e5+10;
6 int ne[maxn];
7 char s[maxn];
8 int l,t;
9 void getnext()
10 {
11 int i=0,j=-1;
12 ne[i]=j;
13 while(i<l)
14 {
15 if(j==-1||s[i]==s[j])
16 {
17 ne[++i]=++j;
18 }
19 else j=ne[j];
20 }
21 }
22 int main()
23 {
24 scanf("%d",&t);
25 while(t--)
26 {
27 scanf("%s",s);
28 l=strlen(s);
29 getnext();
30 if(ne[l]==0) {
31 printf("%d\n",l);
32 continue;
33 }
34 if(l%(l-ne[l])==0) printf("%d\n",0);
35 else printf("%d\n",(l-ne[l])-(l%(l-ne[l])));
36 }
37 }