Finding the longest palindromic subsequence.

Правка en4, от sam_2912, 2022-06-16 05:59:14

One of the approaches to find the Longest Palindromic Subsequence(LPS) in a string is to reverse the string and find the longest common subsequence between the original S and reversed S' strings.

I did some further research and found that it is not necessary that LCS(S,S') outputs the longest palindromic subsequence (LPS), instead the LPS is one of the all possible LCSs between S and S'.

So as long as we just have to find the length of LPS and not the LPS string itself the LCS(S,S') approach works fine. But for that it must be proved that if length of LPS is x then there exists no subsequence greater that length x common between S and S'. How do I mathematically or intuitively prove this?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский sam_2912 2022-06-16 05:59:14 4
en3 Английский sam_2912 2022-06-16 05:58:39 8
en2 Английский sam_2912 2022-06-16 05:20:56 21 Tiny change: 'sible LCSs. So as lo' -> 'sible LCSs between _S_ and _S'_. So as lo'
en1 Английский sam_2912 2022-06-16 05:19:44 813 Initial revision (published)