Friday, March 13, 2015

Longest Palindromic Subsequence


Problem: Given a sequence, find the length of the longest palindromic sub-sequence in it.

Solution: 

Longest Common Sub-sequence can be used to solve this problem. The steps are as follows:
1. Reverse the given sequence and store the reverse in another array say reverse[0..n-1]
2) LCS of the given sequence and reverse[] will be the longest palindromic sequence

Implementation:

int LPS(std::string S)
{
std::string T = S;
std::reverse(T.begin(), T.end());
return LCS(S, T);
}

Please find the implementation of LCS at the following URL:
http://algods-cracker.blogspot.in/2015/03/longest-common-sub-sequencelcs.html

Complexity: O(n2)

No comments:

Post a Comment