Hdu 4763 Theme Section (kmp)

题目链接：

题目描述：

　　给出一个串，问最长的不但是前缀，还是后缀，而且在中间也出现过的串的长度是多少？(出现的这三次不能重叠)

解题思路：

　　利用kmp的next数组，求出不但是前缀而且是后缀的串，然后在剩下的中间串中匹配，如果出现过就找到了答案，否则更新前缀和后缀串，重新匹配。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 
 8 #define LL long long
 9 #define maxn 1000010
10 #define mod 100000007
11 
12 char b[maxn];
13 int Next[maxn], n, m;
14 
15 void Get_Next ()
16 {
17     int i, j;
18     j = Next[0] = -1;
19     i = 0;
20 
21     while (i < m)
22     {
23         while (j!=-1 && b[i]!=b[j])
24             j = Next[j];
25 
26         Next[++ i] = ++ j;
27     }
28 }
29 
30 int kmp ()
31 {
32     Get_Next ();
33 
34     int ans = Next[m];
35 
36     int l = ans, r = m - ans;
37     while (ans)
38     {
39         int i = 0;
40         while (l < r)
41         {
42             while (i!=-1 && b[i]!=b[l])
43                 i = Next[i];
44 
45             i ++, l++;
46 
47             if (ans == i)
48                 return ans;
49         }
50         if (l > r)
51         {
52             ans = Next[ans];
53             l = ans, r = m - ans;
54         }
55     }
56     return 0;
57 }
58 
59 int main ()
60 {
61     int T;
62     scanf ("%d", &T);
63 
64     while (T --)
65     {
66         scanf ("%s", b);
67         m = strlen (b);
68         printf("%d
", kmp ());
69     }
70     return 0;
71 }