/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 vote329 views1 answer
Create a file in a specific directory
Python
0 vote323 views1 answer
Django MESSAGE_TAGS
Python
0 vote316 views1 answer
ModuleNotFoundError: No module named 'myapp' alembic
Python
6 votes360 views3 answers
Replace multiple spaces with single space python
Python
0 vote321 views1 answer
How to print list without newline
Python
0 vote270 views1 answer
Pymongo dynamic structure
Python
0 vote342 views1 answer
System to extract data from csv file in python
Python
13 votes371 views4 answers
How to use if else in lambda python
Python
1 vote310 views2 answers
Matplotlib display graph on jupyter notebook
Python
0 vote358 views1 answer
Add x=y line to scatter plot python
Python