hdu4763 Theme Section(KMP)

简单的next数组的应用

先求出next[n]，然后可以在1-next[n]之间枚举长度

找出不和前缀和后缀重复的中间的最大长度即可

代码：

 1 #include<iostream>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<cstdio>
 5 using namespace std;
 6 
 7 #define maxn 1001000
 8 char s[maxn];
 9 int n;
10 int f[maxn];
11 int length;
12 void callnext()
13 {
14    f[0]=-1;
15    int k=-1,j=0;
16    while(j<length)
17    {
18       if(k==-1 || s[j]==s[k])
19       {
20          j++;k++;
21          f[j]=k;
22       }
23       else  k=f[k];
24    }
25 
26 }
27 int main()
28 {
29    int t;
30    scanf("%d",&t);
31    while(t--)
32    {
33      scanf("%s",s);
34      length=strlen(s);
35      callnext();
36      n=f[length];
37      if(n==0)
38      {
39        printf("0
");
40        continue;
41      }
42      int max_=n;
43      bool flag=0;
44      while(max_)
45      {
46         if(length-max_>max_) 
47         {
48                
49             for(int j=max_;j<=length-max_;j++)
50               if(f[j]==max_ && j-max_>=max_)
51                 {
52                      flag=1;
53                      break;
54                 }
55         }
56         if(flag) break;
57         max_--;
58    
59      }
60     cout<<max_<<endl;
61 
62    }
63    return 0;
64 }