LeetCode 最长回文子字符串

18 九月, 2014 (16:08) | 程序、算法 | By: admin

求一个字符串的最长回文子字符串,网上分析的文章不计其数

这里是LeetCode的原文:http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html#comment-226860

CSDN也有很多,例如这个:http://blog.csdn.net/stephen_wong/article/details/28746107

九章算法,仍然借助了辅助字符串的概念,但没有实际构造一个:http://answer.ninechapter.com/solutions/longest-palindromic-substring/

虽然昨天用C完成了一份,但感觉C写这类代码真是不方便,还是java或者python比较好,希望将来放一个python的版本上来

对于网上的代码,补充一点分析,主要是对于开始几步。先看一下LeetCode的代码:

 

其中,以下这段代码比较好理解,可结合各种文章的分析

但是比较难理解的是初始化条件和初始的判断语句

 

按照辅助字符串构造方法,开始时C和R位于串首’^’处,i位于第一个’#’处,i_mirror位于-1处

此时算法从第一个’#’处记录各个位置的最长回文子串的半径,其实完全可以从P[2]处也即第一个实际字符处开始记录,但这样边界条件的处理会稍微复杂一点。

记住,R代表了目前所找到的回文子串的最右边界,对于每一个原文字符串,P[i]至少为1因为两边有’#’,而对每一个’#’,可能为0.

所以对于i如果等于或者大于R,P[i]肯定是要重新计算了,所以要置0,而如果i没有超过R,则说明i还在当前所有回文子串的最右边界范围内,或者说T[i]位置的字符是被某一个回文子串包含了,而这个字符串的中心就是C。注意,C并不等于i,例如图中C等于11,但i等于15,C为中心的子串半径很大

此时P[i]的值可以参考它的对称点的值,如果对称点为中心的回文子串完全落在C为中心的回文子串范围内,则很显然P[i]=P[i_mirror],如果不是的话,就只能确保i为中心,R为右边界的子串为回文,至于再往两边是不是则需要程序判断了,,所以此时需要设P[i]=R-i,而判断i_mirror为中心的子串是否完全落在C为中心的回文子串范围内,就是比较R-i和P[i_mirror]的大小,实际上R-i等价于i_mirror-L

再回到开始吧,R什么时候大于i?就是找到了某个半径大于1的子串之后而i还没有突破R的边界

R什么时候会小于i?当走到右边界之后还没有找到更新的回文子串,也就是某次循环的末尾i=R,P[i]=0

当下次循环开始的时候,i=R+1,所以此时P[i]=0。

可以看出,初始化时就是i=R+1的情况,所以初始循环条件成立。

补充一下,LeetCode的源码有问题,有人看出来了吗?

说一下吧,如果原文字符串即以’^’开头,而且后面没有回文子串了,那么P[i]=1就是找到的maxLen!

此时取子串时  (centerIndex – 1 – maxLen)/2 被除数会出现负数,虽然不影响具体结果(输出第一个字符),但多多少少算不严谨吧。

解决方法,找P[i]最大值时从i=2开始找即可,因为这才是实际的第一个字符。

 

 

    分享到:

Write a comment





Time limit is exhausted. Please reload CAPTCHA.