题解：P12213 [蓝桥杯 2023 国 Python B] 最长回文前后缀

· · 题解

前言

题目传送门

前置知识： manacher 算法 模板题

推荐练习：P4555 最长双回文串

参考资料：推荐练习的某篇题解

题目描述

给定一个字符串 S，请找出 S 的一个前缀和后缀，使得它们拼接后是一个回文串。请输出这个串的最长长度。

分析

先令 n= |S|

拿到这个题目看数据范围，第一眼可能想到 O(n\log n) 的哈希做法，但前缀和后缀拼接似乎并不好写哈希。

所以我们先考虑把后缀转化一下，尝试令 T 为 S 翻转之后的字符串。

我们可以观察到：拼接之后的回文串将会由两部分组成，

第一部分是 S 与 T 串的公共前缀（可以为空），

第二部分是 S 或 T 串接在这个前缀之后的一个回文串（可以为空）。

对于第一部分，可以从前向后枚举，暴力匹配。

那么我们需要做的就是预处理出两串的每个前缀之后的最长回文串。

我们参考参考资料的做法，对每个字符串跑一遍 manacher ,

在此过程中，我们就可以求出以每个字符（在扩展之后的字符串中）为左端点的 最长饱和回文串 的长度，

然后再从前向后刷一遍，求出对应的 最长回文串 的长度，

最后就是愉快的暴力匹配，统计答案。

此题中有一些细节要处理好，写在注释中了。

code:

#include<bits/stdc++.h>
using namespace std;
#define rei register int
#define N 100005

char a[N],b[N],h1[N<<1],h2[N<<1];//h 是展开数组 
int n,len,p1[N<<1],p2[N<<1],l1[N<<1],l2[N<<1];//p 是半径数组，l 存储最长回文串长度 

void ch(char *x,char *y)//扩展 
{
    rei k=0;y[k++]='$',y[k++]='#';
    for(rei i=0;i<n;i++) y[k++]=x[i],y[k++]='#';
    y[len=k]='&';
}

void manacher(char *op,int *r,int *l) 
{
    int mr=0,c;
    for(rei i=1;i<len;i++)
    {
        if(i<mr) r[i]=min(r[2*c-i],mr-i);
        else r[i]=1;
        while(op[i+r[i]]==op[i-r[i]]) r[i]++;
        if(i+r[i]-1>mr) mr=i+r[i]-1,c=i;
        l[i-r[i]+1]=max(l[i-r[i]+1],r[i]-1);//求出以该点为左端点的最长饱和回文串 
    }
    for(rei i=3;i<len;i+=2) l[i]=max(l[i-2]-2,l[i]);
    //求出以该点为左端点的最长回文串（含饱和回文串与不饱和回文串） 
}

int main()
{
    scanf("%s",a);n=strlen(a);
    int ans=0;
    for(rei i=0;i<n;i++) b[i]=a[n-i-1]; 
    ch(a,h1),manacher(h1,p1,l1);
    ch(b,h2),manacher(h2,p2,l2); 
    for(rei i=2;i<=len;i+=2)
    {
        ans=max(max(i-2+l1[i-1],i-2+l2[i-1]),ans);
        //注意细节处理，l数组只考虑 # 字符，匹配字符只考虑原串字符
        //此时是当前位置还 没有被匹配上 的答案 
        if(h1[i]!=h2[i]) break;
    }
    printf("%d",ans);
    return 0;
}

时间复杂度分析

manacher 算法是 O(n) 的，暴力匹配是 O(n) 的，每一步查询是 O(1) 的，总的复杂度就是 O(n) 的。

当然，也可以用哈希加二分写，时间复杂度就是 O(n\log n) 的。