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 求出以某个节点为中心向左向右最大能扩展的数量,并枚举分隔符判断即可。

 

 

 

发表回复

您的电子邮箱地址不会被公开。