Sample Input

3

aaa

abca

abcde

Sample Output

0

2

5

题目大意：

给你一个字符串，要求将字符串的全部字符最少循环2次需要添加的字符数。

例子：

abcabc 已经循环2次，添加数为0

abcac 没有循环2次，添加字符abcac。数目为5.

abcabcab 已经循环过2次，但第三次不完整，需要添加数为1

 

1 # include 
      
        2 # include 
       
         3 using namespace std; 4  5 char s1[100010] ; 6 int next[100010] ; 7 int tlen ; 8 int xlen ; 9 10 void getNext()11 {12     int j, k;13     j = 0; k = -1; next[0] = -1;14     while(j < tlen)15         if(k == -1 || s1[j] == s1[k])16             next[++j] = ++k;17         else18             k = next[k];19 20 }21 22 int main ()23 {24     int T ;25     int add ;26     scanf("%d" , &T); 27     while (T--)28     {29         scanf("%s" , s1) ;30         tlen = strlen(s1) ;31         getNext() ;32         xlen =tlen - next[tlen] ; //循环节的长度33         if (xlen != tlen && tlen % xlen == 0)34           printf("0\n") ;35         else36         {37             add = xlen - next[tlen] % xlen ;38             printf("%d\n" , add) ;39         }40     }41     42     43     return 0 ;44 }