是的,使用类似 LCS 的算法找到最长的回文并不是一个好方法,我没有仔细阅读引用的答案,但答案中的这一行是完全错误的:
所以字符串中包含的最长回文正是该字符串及其反序列的最长公共子串
但如果你读了它并且你有一个反例,请不要担心(99%你是对的),这是常见的错误,但简单的方法如下:
写下字符串 (barbapapa
) 如下:#b#a#r#b#a#p#a#p#a#
,现在从左到右遍历这个新字符串的每个字符,检查它的左右是否是回文中心。该算法在最坏情况下的时间复杂度为 O(n^2),并且工作完全正确。但通常会在 O(n) 中找到回文(在平均情况下证明这一点确实很困难)。最坏的情况是字符串中有太多长回文,例如aaaaaa...aaaa
.
但是有更好的方法需要 O(n) 时间,该算法的基础是Manacher http://en.wikipedia.org/wiki/Longest_palindromic_substring。相关算法比我在您引用的答案中看到的更复杂。但我提供的是Manacher算法的基本思想,通过算法的巧妙改变,你可以跳过检查所有的左和右(也有使用后缀树的算法)。
P.S:由于我的网络限制,我看不到你的 Algo 链接,我不知道它是否正确。
我添加了与 OP 的讨论以阐明算法:
let test it with barbapapa-> #b#a#r#b#a#p#a#p#a#, start from first #
there is no left so it's center of palindrome with length 1.
Now "b",has # in left and # in right, but there isn't another left to match with right
so it's a center of palindrome with length 3.
let skip other parts to arrive to first "p":
first left and right is # second left and right is "a", third left and
right is # but forth left and right are not equal so it's center of palindrome
of length 7 #a#p#a# is palindrome but b#a#p#a#p is not
Now let see first "a" after first "p" you have, #a#p#a#p#a# as palindrome and this "a"
is center of this palindrome with length 11 if you calculate all other palindromes
length of all of them are smaller than 11
还使用#
是因为考虑偶数长度的回文。
在新创建的字符串中找到回文中心后,找到相关的回文(通过知道中心及其长度),然后删除#
找出最大的回文。