Processing math: 100%

YZOJ P3906 最长双回文串

YZOJ P3906 最长双回文串

时间限制:1000MS      内存限制:131072KB

难度:4.0

  • 题目描述

输入长度为 n 的串 S ,求 S 的最长双回文子串 T,即可将 T 分为两部分 X, Y\left|X\right|, \left|Y\right| \geq 1),且 X, Y 都是回文串。

  • 输入格式

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

  • 输出格式

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

  • 样例输入

  • 样例输出

  • 样例说明

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

  • 数据规模与约定

对于 100\% 的数据, 2 \leq \left|S\right| \leq 10^5

 

 

Source: BZOJ 2565


 

 

 

Manacher 裸题。

正反两遍 Manacher 求出以某个节点为中心向左向右最大能扩展的数量,并枚举分隔符判断即可。

 

 

 

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注