**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(n

^{2})

## No comments:

## Post a Comment