/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

0 vote292 views1 answer
How to instal django cities
Python Django
2 votes273 views1 answer
Python list of all tkinter events
Python
0 vote268 views1 answer
How to end an infinite loop in specific time python
Python
26 votes288 views5 answers
Is_integer Python
Python
0 vote254 views1 answer
Pandas dataframe from array of dict
Python
10 votes286 views4 answers
Discord.py to discord.js converter
Python
2 votes260 views1 answer
AlphaTauri
Python
0 vote298 views1 answer
Python fibonacci sequence for loop
Python
0 vote272 views1 answer
Compute condition number python
Python
0 vote258 views1 answer
Python pandas return column name of a specific column
Python