POJ 3974 Palindrome

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 const int MAXN = 1000010;
 6 char Ma[2*MAXN];
 7 int Mp[2*MAXN];
 8 
 9 void Manacher(char s[], int len)
10 {
11     int l = 0;
12     Ma[l++] = ‘S‘;
13     Ma[l++] = ‘#‘;
14     for (int i = 0; i < len; ++i)
15     {
16         Ma[l++] = s[i];
17         Ma[l++] = ‘#‘;
18     }
19     Ma[l] = 0;
20     int mx = 0;
21     int id = 0;
22     for (int i = 0; i < l; ++i)
23     {
24         Mp[i] = mx > i ? min(Mp[2*id-i], mx-i) : 1;
25         while (Ma[i+Mp[i]] == Ma[i-Mp[i]]) ++Mp[i];
26         if (i + Mp[i] > mx)
27         {
28             mx = i +Mp[i];
29             id = i;
30         }
31     }
32 }
33 
34 char s[MAXN];
35 
36 int main()
37 {
38     int cnt = 0;
39     while (scanf("%s", s) != EOF)
40     {
41         if (strcmp(s, "END") == 0) break;
42         int len = strlen(s);
43         Manacher(s, len);
44         int ans = 0;
45         len = 2 * len + 2;
46         for (int i = 0; i < len; ++i) ans = max(ans, Mp[i] - 1);
47         printf("Case %d: %d\n",++cnt, ans);
48     }
49     return 0;
50 }