URAL 1297 Palindrome（Manacher）

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <iostream>
 5 using namespace std;
 6 typedef long long LL;
 7 
 8 const int MAXN = 2 * 1010;
 9 
10 char str[MAXN], s[MAXN];
11 int n, p[MAXN];
12 
13 void manacher() {
14     int mx = 0, id;
15     for(int i = 1; i < n; ++i) {
16         if(mx > i) p[i] = min(p[2 * id - i], mx - i);
17         else p[i] = 1;
18         while(s[i + p[i]] == s[i - p[i]]) ++p[i];
19         if(i + p[i] > mx) {
20             id = i;
21             mx = i + p[i];
22         }
23     }
24 }
25 
26 void print() {
27     int id = 0;
28     for(int i = 1; i < n; ++i)
29         if(p[i] > p[id]) id = i;
30     int l = (id - p[id] + 1) / 2, r = l + p[id] - 1;
31     for(int i = l; i < r; ++i) putchar(str[i]);
32     puts("");
33 }
34 
35 int main() {
36     scanf("%s", str);
37     s[n++] = ‘$‘, s[n++] = ‘#‘;
38     for(int i = 0; str[i]; ++i) {
39         s[n++] = str[i];
40         s[n++] = ‘#‘;
41     }
42     s[n] = 0;
43     manacher();
44     print();
45 }