Friday, March 13, 2015

Longest Palindromic Subsequence

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


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


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:

Complexity: O(n2)

No comments:

Post a Comment