Clever Geek Handbook

UVa_11151 (longest palindrome)

Does anyone know why the following algorithm works for finding the longest palindrome in a given string? Find the longest common subsequence (substring) of a string and its back. The result is the longest palindrome.

+3


source to share


2 answers


Thank you Bolo! But in your line lcs line and its inverse is 1234A4321 or 1234B4321 which is a palindrome. A palindrome is a common subsequence for a string and its reverse, but I don't know why the (longest) common subsequence is a palindrome.



0


source


It seems to me that the statement is false. Take line 012310. Its back is 013210. The longest common substrings of these two strings are 01 and 10, neither of which is a palindrome. The only palindromes in the original string are trivial substrings of length 1.



0


source






More articles:


All Articles