HDOJ 3026 manacher

链接：

http://acm.hdu.edu.cn/showproblem.php?pid=3068

题意：

找出一个字符串中的最长回文子串

题解：

manacher裸模板

另外以后读取大量的string还是用c风格字符串吧

代码：

31 char s[MAXN], str[MAXN];
32 int len1, len2;
33 int p[MAXN << 1];
34 
35 void init() {
36     str[0] = '$';
37     str[1] = '#';
38     rep(i, 0, len1) str[i * 2 + 2] = s[i], str[i * 2 + 3] = '#';
39     len2 = len1 * 2 + 2;
40     str[len2] = '*';
41 }
42 
43 void manacher() {
44     int id = 0, mx = 0;
45     rep(i, 1, len2) {
46         if (mx > i) p[i] = min(p[2 * id - i], mx - i);
47         else p[i] = 1;
48         for (; str[i + p[i]] == str[i - p[i]]; p[i]++);
49         if (i + p[i] > mx) mx = p[i] + i, id = i;
50     }
51 }
52 
53 int main() {
54     while (scanf("%s", s) != EOF) {
55         len1 = strlen(s);
56         init();
57         manacher();
58         int ans = 0;
59         rep(i, 0, len2) ans = max(ans, p[i]);
60         printf("%d
", ans - 1);
61     }
62     return 0;
63 }