自动搬运

查看原文

来自洛谷，原作者为

	Wxb2010 **

搬运于2025-08-24 23:13:45，当前版本为作者最后更新于2025-05-05 08:13:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

题目传送门

前置知识： 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)$ 的。