P4555 题解

前置知识

单调队列，manacher。

题目分析

本题要求求出两个相邻的最长回文串，不妨考虑对于每一个点求出以它为左端点最长的回文串记为 l_i。对于右边的回文串，从后往前遍历，假设当前枚举到点 i，它的最长回文串的左端点记为 j，那么此时的回文串长度就为 len_i-1+l_j，然后更新答案即可。

那么怎么求左端点最长的回文串呢？

考虑用单调队列维护，从左往右依次加入回文串，l_i 只与回文串中心有关，我们从左往右插入，中心一定是单调的，当此回文串的右端点小于枚举的点，将它弹出队列，画个图给大家理解一下。

绿色的表示中心。

单调队列复杂度 O(n)，manacher 复杂度O(n)，总时间复杂度为 O(n)。

Code

#include<iostream>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<random>
#include<chrono>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef long long LL;
typedef pair<int,int>PII;
const int N=1e5+10;
string s;
char a[N*2];
int n,p[N*2];
int l[N*2];
void init(){
    int len=0;
    a[++len]='^';
    a[++len]='#';
    for(int i=1;i<=n;i++){
        a[++len]=s[i];
        a[++len]='#';
    }
    a[++len]='$';
    n=len;
}
void manacher(){
    int mr=0,mid;
    for(int i=1;i<=n;i++){
        if(i<mr)p[i]=min(mr-i,p[mid*2-i]);
        else p[i]=1;
        while(a[i+p[i]]==a[i-p[i]])p[i]++;
        if(p[i]+i>mr){
            mr=p[i]+i;
            mid=i;
        }
    }
}
PII q[N*2];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>s;
    n=s.length();
    s=' '+s;
    init();
    manacher();
    int hh=0,tt=0;
    for(int i=1;i<=n;i++){
        while(hh<tt&&q[hh].second<i)hh++;
        l[i]=i-q[hh].first;
        if(p[i]>1)q[++tt]={i,i+p[i]-1};
    }
    int ans=0;
    for(int i=n-2;i>2;i--){
        if(i-p[i]+1<=2)continue;
        ans=max(ans,p[i]-1+l[i-p[i]+1]);
    }
    cout<<ans;
    return 0;
}