Theme Section

 1 /* ***********************************************
 2 Author        :kuangbin
 3 Created Time  :2013-9-29 18:18:34
 4 File Name     :E:\2013ACM练习\2013网络赛\2013长春网络赛\1005.cpp
 5 ************************************************ */
 6 
 7 #include <stdio.h>
 8 #include <string.h>
 9 #include <iostream>
10 #include <algorithm>
11 #include <vector>
12 #include <queue>
13 #include <set>
14 #include <map>
15 #include <string>
16 #include <math.h>
17 #include <stdlib.h>
18 #include <time.h>
19 using namespace std;
20 
21 void kmp_pre(char x[],int m,int next[])
22 {
23     int i,j;
24     j = next[0] = -1;
25     i = 0;
26     while(i < m)
27     {
28         while( -1 != j && x[i] != x[j] )j = next[j];
29         next[++i] = ++j;
30     }
31 }
32 char str[1000010];
33 int next[1000010];
34 bool f[1000010];
35 int main()
36 {
37     //freopen("in.txt","r",stdin);
38     //freopen("out.txt","w",stdout);
39     int T;
40     scanf("%d",&T);
41     while(T--)
42     {
43         scanf("%s",str);
44         int n = strlen(str);
45         kmp_pre(str,n,next);
46         memset(f,false,sizeof(f));
47         int tmp = n;
48         while(tmp > 0)
49         {
50             if(n >= 2*tmp)f[tmp] = true;
51             tmp = next[tmp];
52         }
53         int ans = 0;
54         for(int i = n-1;i > 1;i--)
55         {
56             tmp = i;
57             while(tmp > 0)
58             {
59                 if(f[tmp] && i >= 2*tmp && n >= i+tmp)
60                 {
61                     ans = max(ans,tmp);
62                     break;
63                 }
64                 tmp = next[tmp];
65             }
66         }
67         printf("%d\n",ans);
68     }
69     return 0;
70 }