BZOJ2565 最长双回文串 < Manacher >

Problem

最长双回文串

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

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

Input

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

Output

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

Sample Input

baacaabbacabb

Sample Output

12

Explanation

从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分，且两者都是回文串。

HINT

对于$100\%$的数据，$2\le|S|\le10^5$
$2015.4.25$新加数据一组

Source

$2012$国家集训队$\mathrm{Round\;1\;Day\;2}$

标签：Manacher

Solution

$\mathrm{Manacher}$上稍加变化。

首先跑$\mathrm{Manacher}$得到以每个位置为中心的回文串最大长度。然后考虑计算出$\lbrace L\rbrace$和$\lbrace R\rbrace$，分别表示以每个位置为终点和起点的最长回文串的中心点位置。如此枚举每个位置作为中间断点打擂得到最长双回文字串。

那么如何计算$\lbrace L\rbrace$和$\lbrace R\rbrace$呢？
对于位置$i$，其最长回文串半径长为$r_i$，那么区间$[i,i+r_i)$中的所有位置都可以作为这个串的右端点（终点）。于是这些位置的$L$值一定不大于$i$，这是因为$L$值越小，回文串越长，这样更优。所以从前往后枚举$i$，如果$[i,i+r_i)$中的某个点的$L$值在前面没有确定到，那么这个点的$L$值一定最小为$i$。发现这样的点一定在一个区间中，所以可以记录每次更新$L$更新到的位置，即可$O(n)$扫一遍得到$\lbrace L\rbrace$。反着这样扫一遍即可得到$\lbrace R\rbrace$。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
#define MAX_M 200000
using namespace std;
char s[MAX_M+5];
int n, f[MAX_M+5];
int L[MAX_N+5], R[MAX_N+5];
void manacher() {
    int p = 0, r = 0;
    for (int i = 1; i <= n; i++) {
        f[i] = i < r ? min(f[p*2-i], r-i) : 1;
        while (i-f[i] >= 1 && i+f[i] <= n)
            if (s[i-f[i]] == s[i+f[i]]) f[i]++;
            else break;
        if (i+f[i] > r) p = i, r = i+f[i];
    }
}
int main() {
    char str[MAX_N+5]; scanf("%s", str), n = (int)strlen(str);
    for (int i = 0; i < n; i++) s[i*2+1] = '#', s[i*2+2] = str[i];
    s[n = n*2+1] = '#', manacher(); int mx = 1, mi = n, ans = 0;
    for (int i = 1; i <= n; i++)
        if (f[i] > 1 && i+f[i] > mx) {
            for (int j = mx; j < i+f[i]; j++) L[j] = i;
            mx = i+f[i];
        }
    for (int i = n; i >= 1; i--)
        if (f[i] > 1 && i-f[i] < mi) {
            for (int j = mi; j > i-f[i]; j--) R[j] = i;
            mi = i-f[i];
        }
    for (int i = 1; i <= n; i++) ans = max(ans, R[i]-L[i]);
    return printf("%d\n", ans), 0;
}