P4555 题解

Cx114514 · 2024-11-02 09:11:58 · 题解

P4555 [国家集训队] 最长双回文串 题解

补一个题解区没有的做法。

记字符串长度为 len。

首先可以用 Manacher 预处理出以每个点为中心的最长回文串，左右端点分别记为 L_{i} 和 R_{i}。 而题目要求最长双回文串。套路地，枚举两个回文串拼接起来的位置，记为 pos。而这两个回文串分别满足左侧最长和右侧最长，形式化地，对于每个 pos，要求 \min\limits_{i\in\left[1,pos\right),R_{i}\ge pos}i 和 \max\limits_{i\in\left(pos,len\right],L_{i}\le pos}i，这是前缀/后缀最小/大值的形式，可以选择用树状数组维护，时间复杂度 O\left(n\log n\right)。

代码部分：

#include <bits/stdc++.h>
using namespace std;

string s;

int len, ans, p[200005], tree[200005], L[200005], R[200005];

int lowbit(int x)
{
    return x & -x;
}

void update(int u, int x)
{
    while (u <= len)
    {
        tree[u] = max(tree[u], x);
        u += lowbit(u);
    }
}

int query(int u)
{
    int res = 0;
    while (u > 0)
    {
        res = max(res, tree[u]);
        u -= lowbit(u);
    }
    return res;
}

int main()
{
    cin >> s;
    len = s.size();
    s = '$' + s;
    s = s + s;
    for (int i = len; i >= 1; i--)
        s[2 * i] = s[i];
    for (int i = 1; i <= len * 2 + 1; i += 2)
        s[i] = '#';
    len = 2 * len + 1;
    for (int t = 1, mid = 0, r = 0; t <= len; t++)
    {
        if (t <= r) p[t] = min(p[mid * 2 - t], r - t + 1);
        while (s[t - p[t]] == s[t + p[t]]) p[t]++;
        if (t + p[t] > r) 
        {
            r = t + p[t] - 1; 
            mid = t;
        }
    }
    for (int i = 1; i <= len; i++)
    {
        if (s[i] == '#') L[i] = len - query(len - i + 1) + 1;
        int r = i + p[i] - 1;
        update(len - r + 1, len - i + 1);
    }
    for (int i = 1; i <= len; i++)
        tree[i] = 0;
    for (int i = len; i >= 1; i--)
    {
        if (s[i] == '#') R[i] = query(i);
        int l = i - p[i] + 1;
        update(l, i);
    }
    for (int i = 1; i <= len; i++)
        if (s[i] == '#') ans = max(ans, R[i] - L[i]);
    cout << ans << endl;
    return 0;
}