最长回文(HDU-3068)

题面

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

输入

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

输出

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

样例输入

1aaaa
2
3abab

样例输出

14
23

提示

无

思路

Manacher模板题。

代码

 1char s[mxn], t[mxn];
 2int p[mxn];
 3
 4int manacher_init(char *s, char *t, int n)
 5{
 6    int j = 2; t[0] = '$', t[1] = '#';
 7    for (int i=0; i<n; i++)
 8    {
 9        t[j++] = s[i];
10        t[j++] = '#';
11    }
12    t[j] = '\0';
13    return j;
14}
15
16int manacher(char *t, int *p, int n)
17{
18    int id = 0, mx = 0, ans = 0;
19    for (int i=1; i<=n; i++)
20    {
21        p[i] = i<mx ? min(p[2*id-i], mx-i) : 1;
22
23        while (t[i+p[i]] == t[i-p[i]]) p[i]++;    // 中心扩展
24
25        if (mx < i+p[i])
26            mx = i+p[i], id = i;
27
28        ans = max(ans, p[i]);
29    }
30    return ans-1;
31}
32
33int main()
34{
35    while(~scanf("%s", s))
36    {
37        int n = manacher_init(s, t, strlen(s));
38        printf("%d\n", manacher(t, p, n));
39    }
40
41    return 0;
42}