JZOJ2682 - [WC2012选拔12.17]最长双回文串

JZOJ2682 - Click Here

  

Description

  顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串,而abc不是(abc的顺序为“abc”,逆序为“cba”,不相同)。

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

  

Input

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

  

Output

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

  

Solutions

  考虑枚举双回文子串的分界点$i$,则该分界点能产生的最大双回文子串为以$i$为结尾的最长回文子串和以$i+1$为开始的最长回文子串。

  这个可以使用回文树解决,分别对正串和反串求一次回文树即可。(其实Manacher也能求)

  

CODE

CODE - Click Here

本站总访问量次 | 本站访客数人次

Powered by Hexo | Designed by iTimeTraveler | Refined by CSHwang