hdu 4763 kmp ***

找AEAEA形式的字符串最长的A长度，E可以为空
只可意会，不可言传，懂kmp即可
 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <queue>
 7 #include <set>
 8 #include <map>
 9 #include <string>
10 #include <math.h>
11 #include <stdlib.h>
12 #include <time.h>
13 using namespace std;
14 #define cl(a) memset(a,0,sizeof(a))
15 #define ts printf("*****
");
16 void kmp_pre(char x[],int m,int nextt[])
17 {
18     int i,j;
19     j = nextt[0] = -1;
20     i = 0;
21     while(i < m)
22     {
23         while( -1 != j && x[i] != x[j] )j = nextt[j];
24         nextt[++i] = ++j;
25     }
26 }
27 char str[1000010];
28 int nextt[1000010];
29 bool f[1000010];
30 int main()
31 {
32     #ifndef ONLINE_JUDGE
33     freopen("1.in","r",stdin);
34     #endif
35     int T;
36     scanf("%d",&T);
37     while(T--)
38     {
39         scanf("%s",str);
40         int n = strlen(str);
41         kmp_pre(str,n,nextt);
42         memset(f,false,sizeof(f));
43         int tmp = n;
44         while(tmp > 0)
45         {
46             if(n >= 2*tmp)
47             {
48                 f[tmp] = true;
49             }
50             tmp = nextt[tmp];
51         }
52         int ans = 0;
53         for(int i = 2;i <n-1;i++)
54         {
55             tmp = i;
56             while(tmp > 0)
57             {
58                 if(f[tmp] && i >= 2*tmp && n >= i+tmp)
59                 {
60                     ans = max(ans,tmp);
61                     break;
62                 }
63                 tmp = nextt[tmp];
64             }
65         }
66         printf("%d
",ans);
67     }
68     return 0;
69 }