P4555 最长双回文串

题目描述

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为abc，逆序为cba，不相同）。

输入长度为$n$的串$S$，求$S$的最长双回文子串$T$,即可将$T$分为两部分$X$，$Y$，（$X,Y≥1$）且$X$和$Y$都是回文串。

输入格式

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

输出格式

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

样例 #1

样例输入 #1

baacaabbacabb

样例输出 #1

提示

【样例说明】

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

对于100%的数据，$2≤S≤10^5

分析

我们使用Manacher算法，$O(n)$ 计算出每个点的最长回文长度。并且同时维护另外两个数组：$hl[i]$ 表示为以 $i$ 为首的最长回文串长度，$tl[i]$ 表示为以 $i$ 为尾的最长回文串长度。

在每次计算出 $p[i]$ 时，同时更新这两个数组。最后分别以 $O(n)$ 的方式处理出这两个数组的所有位，这样我们就可以枚举所有的 “#“ 来得出答案

代码实现

/*
 * @FileName: P4555.cpp
 * @Author: Foresc
 * @Date: 2022/08/18 15:48:46
 */

// Manacher
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#define ll long long
#define ull unsinged long long
#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
typedef std::pair<int,int> PII;
typedef std::pair<double, int> PDI;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
const double PI = 3.14159265358979323846;
int dx[4]={-1, 0, 1, 0};
int dy[4]={0, 1, 0, -1};

using namespace std;

const int N = 2e5 + 10;
int p[N], hl[N], tl[N];
char s[N], t[N]; 

int main()
{
    scanf("%s", t);
    int cnt = 0, len = strlen(t), ans = 0;
    s[cnt++] = '#';
    for(int i = 0; i < len; ++i)
    {
        s[cnt++] = t[i];
        s[cnt++] = '#';
    }
    for(int i = 0, l = 0, r = -1; i < cnt; ++i)
    {
        int m = l + r - i;
        p[i] = max(min(p[m], m - l + 1), 1);
        if(m - p[m] < l)
        {
            while(i - p[i] >= 0 && i + p[i] < cnt && s[i + p[i]] == s[i - p[i]])
                p[i]++;
            l = i - p[i] + 1, r = i + p[i] - 1;
        }
        // 因为 p[i] 是以该点为中心的回文半径
        // 所以该点的回文长度就是 p[i] - 1 (因为总会计算两边的 '#', 所以要减去)、
        // 所以每次我们都取 p[i] - 1 和原值中的较大值即可（原位置可能已经为一个回文的首尾）
        hl[l] = max(hl[l], p[i] - 1);
        tl[r] = max(tl[r], p[i] - 1);
    }
    // 对于为一个长度为 x 的回文的首的位置 i 来说
    // 以 i + 1 位置为首的回文在减去 i 位置的字母之外
    // 还要减去对应的尾部的字母（回文嘛，第一个和最后一个总是要一起加入或者删除）
    // 也就是如以 i 为首回文 abccba, 变成以 i + 1 为首的回文后为 bccb 而不是 bccba
    // 所以对于每一个位置来说，都为上一个位置的长度 - 2 和 0 中较大的值（回文长度总不能是负数把）
    for(int i = 2; i < cnt; i += 2)
        hl[i] = max(hl[i], hl[i - 2] - 2);
    // 以 i 为尾的回文和上面一样，不过是从字符串尾部开始求
    for(int i = len - 4; i >= 0; i -= 2)
        tl[i] = max(tl[i], tl[i + 2] - 2);
    // 最后枚举字符串中的每一个 '#'(天然的分隔点)即可
    for(int i = 0; i < cnt; i += 2)
        if(tl[i] && hl[i])
            ans = max(ans, tl[i] + hl[i]);
    cout << ans << endl;
    return 0;
}