请教palindrome算法# Programming - 葵花宝典
t*e
1 楼
问题如下：
Given a string 's = s1s2...sn', then the longest common subsequence of 's'
and its reverse 'R(s)' is also the longest palindromic subsequence in 's'.
e.g. the longest palindromic subsequence of string 's=abcadd' is 'aba'.
我觉得这个算法用来寻找longest palindromic subsequence (not substring)是很方
便的(Complexity O(n^2))，但是没有想出如何证明算法的正确性，想请教高手帮忙,谢
谢了.
Given a string 's = s1s2...sn', then the longest common subsequence of 's'
and its reverse 'R(s)' is also the longest palindromic subsequence in 's'.
e.g. the longest palindromic subsequence of string 's=abcadd' is 'aba'.
我觉得这个算法用来寻找longest palindromic subsequence (not substring)是很方
便的(Complexity O(n^2))，但是没有想出如何证明算法的正确性，想请教高手帮忙,谢
谢了.