Solution

记录下以每个字符开头/结尾的回文串的最大长度即可。

Code

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 300000;
char t[N];
char s[N];
void init() {
    scanf("%s", t);
    int len = strlen(t);
    for(int i=0; i<len; i++) {
        s[2*i] = '#';
        s[2*i+1] = t[i];
        s[2*i+2] = '#';
        s[2*i+3] = '\0';
    }
}
int r[N];
int ls[N], rs[N];
void manacher() {
    int len = strlen(s);
    int rmax = 0;
    int pos = 0;
    for(int i=0; i<len; i++) {
        if(i < rmax) r[i] = min(r[2*pos-i], rmax-i+1);
        else r[i] = 1;
        while(i-r[i] >= 0 && i+r[i]<len && s[i-r[i]] == s[i+r[i]])
            r[i] += 1;
        if(r[i] + i - 1 > rmax) {
            rmax = r[i] + i - 1;
            pos = i;
        }
        rs[i-r[i]+1] = max(rs[i-r[i]+1], r[i]-1);
        ls[i+r[i]-1] = max(ls[i+r[i]-1], r[i]-1);
    }
    for(int i=0; i<len; i+=2) {
        rs[i] = max(rs[i], rs[i-2]-2);
    }
    for(int i=len-1; i>=0; i-=2) {
        ls[i] = max(ls[i], ls[i+2]-2);
    }
}
int main() {
    init();
    manacher();
    int len = strlen(s);
    int ans = 0;
    for(int i=0; i<len; i+=2) {
        if(ls[i] && rs[i]) ans = max(ans, ls[i] + rs[i]);
    }
    printf("%d\n", ans);
    return 0;
}

Description

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串,而abc不是(abc的顺序为“abc”,逆序为“cba”,不相同)。
输入长度为n的串S,求S的最长双回文子串T,即可将T分为两部分X,Y,(|X|,|Y|≥1)且X和Y都是回文串。

Input

一行由小写英文字母组成的字符串S。

Output

一行一个整数,表示最长双回文子串的长度。

Sample Input

baacaabbacabb

Sample Output

12

HINT

样例说明
从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分,且两者都是回文串。
对于100%的数据,2≤|S|≤10^5
2015.4.25新加数据一组