/Python/Longest Palindromic Substring using DP

Longest Palindromic Substring using DP

# The value of table[i][j] is true, if the substring is palindrome, otherwise false.
# To calculate table[i][j], check the value of table[i+1][j-1], if the value is true and str[i] is same as str[j], then we make table[i][j] true.


# Python program

import sys

# A utility function to print a
# substring str[low..high]
def printSubStr(st, low, high) :
    sys.stdout.write(st[low : high + 1])
    sys.stdout.flush()
    return ''

# This function prints the longest palindrome
# substring of st[]. It also returns the length
# of the longest palindrome
def longestPalSubstr(st) :
    n = len(st) # get length of input string

    # table[i][j] will be false if substring 
    # str[i..j] is not palindrome. Else 
    # table[i][j] will be true
    table = [[0 for x in range(n)] for y
                          in range(n)] 
    
    # All substrings of length 1 are
    # palindromes
    maxLength = 1
    i = 0
    while (i < n) :
        table[i][i] = True
        i = i + 1
    
    # check for sub-string of length 2.
    start = 0
    i = 0
    while i < n - 1 :
        if (st[i] == st[i + 1]) :
            table[i][i + 1] = True
            start = i
            maxLength = 2
        i = i + 1
    
    # Check for lengths greater than 2. 
    # k is length of substring
    k = 3
    while k <= n :
        # Fix the starting index
        i = 0
        while i < (n - k + 1) :
            
            # Get the ending index of 
            # substring from starting 
            # index i and length k
            j = i + k - 1
    
            # checking for sub-string from
            # ith index to jth index iff 
            # st[i + 1] to st[(j-1)] is a 
            # palindrome
            if (table[i + 1][j - 1] and 
                      st[i] == st[j]) :
                table[i][j] = True
    
                if (k > maxLength) :
                    start = i
                    maxLength = k
            i = i + 1
        k = k + 1
    print "Longest palindrome substring is: ", printSubStr(st, start,
                                               start + maxLength - 1)

    return maxLength # return length of LPS


# Driver program to test above functions
st = "forgeeksskeegfor"
l = longestPalSubstr(st)
print "Length is:", l

# This code is contributed by Nikita Tiwari.

Source: geeksforgeeks.org

Similar codes

23 votes188 views4 answers
Django runserver
Python
17 votes205 views5 answers
Convert numpy array to tensor
Python
1 vote281 views1 answer
Create dict from two lists
Python
0 vote185 views1 answer
Python open file exception
Python
0 vote202 views4 answers
Python call function in class
Python
0 vote214 views1 answer
Rotate image pyqt5
Python
8 votes225 views1 answer
Python generate uid
Python
0 vote1.3K views1 answer
Lcd screen 3.5 inch to pi
Python
0 vote183 views1 answer
Pandas change period to daily frequency
Python
0 vote220 views1 answer
Chatbot in python github
Python