Longest palidromic subsequence

From Algorithmist
Jump to navigation Jump to search

Longest Palindromic Subsequence is the problem of finding the longest palindromic subsequence of a sequence.

The solution utilizes dynamic programming.

Overview[edit]

The problem is usually defined as:

Given a sequence of items, find the length of the longest subsequence which is a palindrome. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, in the string abcdefg, "abc", "abg", "bdf", "aeg" are all subsequences.

Recursive solution[edit]

psuedo code:

def lps_len(m, n,S):
    """This function returns length of longest palindromic sequence of x and y."""
    if n==m:
        return 1
    if S[m]==S[n] and m+1==n:
        return 2
    if S[m]==S[n]:
        return lps(m+1,n-1,S)+2
    else:
        return max(lps(m+1,n,S),lps(m,n-1,S)

Dynamic programming[edit]

pseudo code:

def lps(S):
    n = len(S)
    LPS=[[0]*n]*n
    for i in range(n):
        LPS[i][i]=1
    for i in range(n-1,-1,-1):
        for j in range(i+1,n):
            if S[i]==S[j]:
                LPS[i][j]=2+LPS[i+1][j-1]
            else:
                LPS[i][j]=max(LPS[i+1][j],LPS[i][j-1])
     return LPS[0][n-1]

Further reading[edit]