111qqz的小窝

老年咸鱼冲锋!

BZOJ 2565: 最长双回文串 (回文自动机)

Description

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串,而abc不是(abc的顺序为“abc”,逆序为“cba”,不相同)。
输入长度为n的串S,求S的最长双回文子串T,即可将T分为两部分X,Y,(|X|,|Y|≥1)且X和Y都是回文串。

Input

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

Output

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

Sample Input

baacaabbacabb

Sample Output

12

HINT

样例说明

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

对于100%的数据,2≤|S|≤10^5

2015.4.25新加数据一组

Source

 

 

思路:

我们考虑增量构建PAM的时候

构建到pos,当前的状态的len其实就是到以pos位置结尾的最长回文串的长度。

那么我们只需要正着做一遍,再倒着做一遍,然后枚举断点就行了。

时间复杂度O(n)

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz