Wednesday, July 6, 2016

Largest palindromic subsequence in pyhton

# link site is http://www.geeksforgeeks.org/dynamic-programming-set-12-longest-palindromic-subsequence/


def lps(str):
    n = len(str)

    L = [[0 for col in range(n)] for row in range(n)]

    for i in range(n):
        L[i][i] =1
    #count    for cl in range(2, n+1):
         for i in range(0, n-cl+1):
            j= i+cl-1
            if str[i] == str[j] and cl ==2 :
                L[i][j] =2            elif str[i] == str[j]:
                 L[i][j] = L[i+1][j-1] + 2            else :
                L[i][j] = max(L[i][j-1], L[i+1][j])
    print(L)
    return L[0][n-1];

print(lps("ABACAA"))

No comments:

Post a Comment