最长回文

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 11870 Accepted Submission(s): 4351

Problem Description

给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等

Input

输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000

Output

每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.

Sample Input

aaaa

abab

Sample Output

4
3

Manacher算法的模版题，刚模仿着写了个，趁热用一下

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <cmath>
 7 #include <queue>
 8 #include <map>
 9 #include <stack>
10 #include <list>
11 #include <vector>
12 
13 using namespace std;
14 
15 const int maxn = 1000010;
16 int pre[maxn];
17 char str[maxn];
18 char tmp[maxn*2];
19 
20 inline int min(int x, int y) {
21     return x < y ? x : y;
22 }
23 
24 int init(char *tmp, char *str) {
25     int len = strlen(str);
26     tmp[0] = '$';
27     for(int i = 0; i <= len; i++) {
28         tmp[2*i+1] = '#';
29         tmp[2*i+2] = str[i];
30     }
31     tmp[2*len+2] = 0;
32     len = 2 * len + 2;
33     return len;
34 }
35 
36 void manacher(int *pre, char *tmp, int len) {
37     int id = 0;
38     int mx = 0;
39     for(int i = 1; i < len; i++) {
40         pre[i] = mx > i ? min(pre[2*id-i], mx-i) : 1;
41         while(tmp[i+pre[i]] == tmp[i-pre[i]]) {
42             pre[i]++;
43         }
44         if(pre[i] + i > mx) {
45             id = i;
46             mx = pre[i] + id;
47         }
48     }
49 }
50 
51 int main() {
52     // freopen("in", "r", stdin);
53     while(~scanf("%s", str)) {
54         memset(pre, 0, sizeof(pre));
55         memset(tmp, 0, sizeof(tmp));
56         int len = init(tmp, str);
57         manacher(pre, tmp, len);
58         int ans = 1;
59         for(int i = 0; i < len; i++) {
60             ans = max(ans, pre[i]);
61         }
62         printf("%d
", ans - 1);
63     }
64 }