给定一个字符串,例如cabbak,找出其中最长的回文字符串,也就是abba,除了abba这种的,aba也是回文字符串,所谓回文字符串就是指左右两边相同的一种特殊字符串。

思路分析

我们先将字符串进行特定格式的填充,将每个字符串之间填充一个#:

background Layer 1 babcbabcbaccba 原字符串 填充#后 #b#a#b#c#b#a#b#c#b#a#c#c#b#a#

这样的填充是为了可以创造一个唯一的中心点(aba的中心点为b,但是abba不好确定中心点,引入#后,#a#b#b#a很容易确定中心点),并且围绕着这个中心点辐射周边范围为r的区域,在这个区域里左右两边肯定是对称的。我们这里要引入一个概念p,p[i]表示第i个元素的半径(回文字符串是对称的)。

background Layer 1 #a#c#b#a#a#b#c#a# 中心点 r=8 中心点左右8个字符位置范围内对称 我们记中心点p[8]=8,表示它的r=8

现在我们要做一个很大胆的猜测,如何利用对称属性快速获取现在的p[i],这里要介绍一些概念:最近的中心点c以及辐射半径r,就是我们每次在找p[i]的时候,我们都要营造出一个已知的回文字符串,这样才能利用对称性快速找到p[i];镜像i',这是在对称性的时候,利用c,可以找到和i对应的i',这样才能利用p[i']快速估算出现在的p[i]。

background Layer 1 #b#a#b#a#b#a#b#a#c#f c r=7 p 1 0 0 1 0 5 0 7 0 7 ? i i' 我们找到了最近一个可以覆盖当前位置(i)的回文范围(中心为c,p为7) 我们在这个回文范围中找到了镜像元素i',因为i'我们已经计算过,为0,因此此时i位置的p也为0。 这个是显而易见的,因为中心点为c,半径为7,完整覆盖了i',i'的回文范围并没有超过c的回文范围, 因此p[i]=0 #b#a#b#a#b#a#b#a#c#f c r=7 p 1 0 0 1 0 5 0 7 0 7 0 i i' 我们现在来看i位置的p,首先还是找到镜像位置i',p[i']=7,但是i位置的最大回文半径为5(虚线位置) ? r=7 为什么呢?因为根据对称可以知道,在以c为中心,r=7的范围内,i和i'完成相同,但是在这个范围之外 就是不确定的,然后i'的回文范围已经超过了c的回文范围,因此我们最多只能断定p[i]>=5 也就是p[i]=Math.min(p[i'],r-i)

完整代码

其他文章

0
我要评论

评论

返回
×

我要评论

回复:

昵称:(昵称不超过20个字)

图片:

提交
还可以输入500个字