1 回答
Yes, finding longest palindrome by using LCS like algorithms is not a good way, I didn't read referenced answer carefully but this line in the answer is completely wrong:
So the longest contained palindrome within a string is exactly the longest common substring of this string and its reverse
but if you read it and you have a counter example don't worry about it (you are right in 99%), this is common mistake, But simple way is as follow:
Write down the string (barbapapa) as follow: #b#a#r#b#a#p#a#p#a#, now traverse each character of this new string from left to right, check its left and right to check whether it's a palindrome center or not. This algorithm is O(n^2) in worst case and works perfectly correct. but normally will finds palindrome in O(n) (sure proving this in average case is hard). Worst case is in strings with too many long palindromes like aaaaaa...aaaa.
But there is better approach which takes O(n) time, base of this algorithm is by Manacher. Related algorithm is more complicated than what I saw in your referenced answer. But what I offered is base idea of Manacher algorithm, with clever changes in algorithm you can skip checking all left and rights (also there are algorithms by using suffix trees).
P.S: I couldn't see your Algo link because of my internet limitations, I don't know it's correct or not.
I added my discussion with OP to clarify the algorithm:
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
Also using # is because considering palindromes of even length.
After finding center of palindrome in newly created string, find related palindrom (by knowing the center and its length), then remove # to find out biggest palindrome.