UVa_11151 (самый длинный палиндром)

Question

Кто-нибудь знает, почему следующий алгоритм работает для нахождения самого длинного палиндрома в данной строке?Найдите самую длинную общую подпоследовательность (подстроку) строки и ее обратную сторону.Результат - самый длинный палиндром.

Answer 1

Мне кажется, что утверждение неверно.Возьмем строку 012310. Ее обратная сторона - 013210. Самые длинные общие подстроки этих двух строк - 01 и 10, ни одна из которых не является палиндромом.Единственными палиндромами в исходной строке являются тривиальные подстроки длины 1.

Answer 2

Спасибо, Боло! Но в вашей строке lcs строки и ее обратного значения - либо 1234A4321, либо 1234B4321, который является палиндромом. Палиндром - это общая подпоследовательность для строки и ее обратного, но я не знаю, почему (самая длинная) общая подпоследовательность является палиндромом.