1 // File Name: getnext.cpp 2 // Author: darkdream 3 // Created Time: 2014年09月09日 星期二 22时35分02秒 4  5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 #define LL long long25 26 using namespace std;27 char str[300004];28 int next[300005];29 void getnext()30 {31     int len = strlen(str);32     next[0] = -1; 33     int k = -1;34     int j = 0 ;35     int sum = 0 ; 36     while(j <= len - 1)37     {38         if(k == -1 || str[j] == str[k])39         {40             ++j; 41             ++k;42             next[j] = k ;43         }44         else {45             k = next[k];46         }47     }48 /*    for(int i = 0 ;i <= len; i ++)49         printf("%d ",next[i]);50     printf("\n");*/51     int t = len - next[len];52     if(next[len]%t == 0 && len/t != 1)53     {54         printf("0\n");55     }else{56         printf("%d\n",((next[len]/t+1) * t -next[len]));57     }58 59 }60 int main(){61     int t; 62     scanf("%d",&t);63     while(t--)64     {65         scanf("%s",str);66         getnext();67     }68     return 0;69 }