题目地址：洛谷：【P4555】最长双回文串 – 洛谷、BZOJ：Problem 2565. — 最长双回文串

题目描述

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

输入输出格式

输入格式：
一行由小写英文字母组成的字符串S。

输出格式：
一行一个整数，表示最长双回文子串的长度。

输入输出样例

输入样例#1：

baacaabbacabb

输出样例#1：

12

说明

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

题解

为了这题学了一波Manacher。我们考虑处理出一个#占位符为起始、终止位置的最长回文串长，只需要枚举这个占位符把两个数据加起来再求最大值，就得到了答案。
接下来我们考虑计算上面的数据，对于每一个位置我们可以知道p[i]-1表示该位置为中心的回文串最大半径，那么需要更新[i-p[i]+1, i+p[i]-1]这段区间内的所有位置的数据。这样做复杂度会很高，因此我们考虑只在端点更新信息，之后用一个递推推过来。
递推的过程是，假如ls[i]表示i位置为结尾的最长回文串长，则可以从ls[i+2]-2来逆推更新当前位置的值。
总复杂度为O(n)。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

const int MAXN = 200005;

char s1[MAXN], s2[MAXN];
int n, tot, p[MAXN], rs[MAXN], ls[MAXN], mx;

int main() {
    scanf("%s", s1 + 1); n = strlen(s1 + 1);
    s2[tot++] = '$'; s2[tot++] = '#';
    for(int i = 1; i <= n; i++) {
        s2[tot++] = s1[i]; s2[tot++] = '#';
    }
    int mxlen = 0, mx = 0, id;
    for(int i = 1; i < tot; i++) {
        if(i < mx) p[i] = std::min(p[(id << 1) - i], mx - i);
        else p[i] = 1;
        while(s2[i - p[i]] == s2[i + p[i]]) p[i]++;
        if(mx < i + p[i]) {
            id = i; mx = i + p[i];
        }
        rs[i - p[i] + 1] = std::max(rs[i - p[i] + 1], p[i] - 1);
        ls[i + p[i] - 1] = std::max(ls[i + p[i] - 1], p[i] - 1);
    }
    for(int i = 1; i < tot; i += 2) {
        rs[i] = std::max(rs[i], rs[i - 2] - 2);
    }
    for(int i = tot; i > 1; i -= 2) {
        ls[i] = std::max(ls[i], ls[i + 2] - 2);
    }
    int ans = 0;
    for(int i = 1; i < tot; i += 2) {
        if(ls[i] && rs[i]) ans = std::max(ans, ls[i] + rs[i]);
    }
    printf("%d", ans);
    return 0;
}