Longest Palindromic Substring Python

PROGRAM TO FIND THE LONGEST PALINDROMIC SUBSTRING

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




OUTPUT

Longest palindrome substring is: geeksskeeg
Length is: 10

CREDITS: https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/