Manacher 's Algorithm | Python program to implement Manacher 's Algorithm ; Position count ; LPS Length Array ; centerPosition ; centerRightPosition ; currentRightPosition ; currentLeftPosition ; Uncomment it to print LPS Length array printf ( " % d ▁ % d ▁ " , L [ 0 ] , L [ 1 ] ) ; ; get currentLeftPosition iMirror for currentRightPosition i ; If currentRightPosition i is within centerRightPosition R ; Attempt to expand palindrome centered at currentRightPosition i Here for odd positions , we compare characters and if match then increment LPS Length by ONE If even position , we just increment LPS by ONE without any character comparison ; Track maxLPSLength ; If palindrome centered at currentRightPosition i expand beyond centerRightPosition R , adjust centerPosition C based on expanded palindrome . ; Uncomment it to print LPS Length array printf ( " % d ▁ " , L [ i ] ) ; ; Driver program
def findLongestPalindromicString ( text ) : NEW_LINE INDENT N = len ( text ) NEW_LINE if N == 0 : NEW_LINE INDENT return NEW_LINE DEDENT N = 2 * N + 1 NEW_LINE L = [ 0 ] * N NEW_LINE L [ 0 ] = 0 NEW_LINE L [ 1 ] = 1 NEW_LINE C = 1 NEW_LINE R = 2 NEW_LINE i = 0 NEW_LINE iMirror = 0 NEW_LINE maxLPSLength = 0 NEW_LINE maxLPSCenterPosition = 0 NEW_LINE start = - 1 NEW_LINE end = - 1 NEW_LINE diff = - 1 NEW_LINE for i in xrange ( 2 , N ) : NEW_LINE INDENT iMirror = 2 * C - i NEW_LINE L [ i ] = 0 NEW_LINE diff = R - i NEW_LINE if diff > 0 : NEW_LINE INDENT L [ i ] = min ( L [ iMirror ] , diff ) NEW_LINE DEDENT try : NEW_LINE INDENT while ( ( i + L [ i ] ) < N and ( i - L [ i ] ) > 0 ) and ( ( ( i + L [ i ] + 1 ) % 2 == 0 ) or ( text [ ( i + L [ i ] + 1 ) / 2 ] == text [ ( i - L [ i ] - 1 ) / 2 ] ) ) : NEW_LINE INDENT L [ i ] += 1 NEW_LINE DEDENT DEDENT except Exception as e : NEW_LINE INDENT pass NEW_LINE DEDENT if L [ i ] > maxLPSLength : NEW_LINE INDENT maxLPSLength = L [ i ] NEW_LINE maxLPSCenterPosition = i NEW_LINE DEDENT if i + L [ i ] > R : NEW_LINE INDENT C = i NEW_LINE R = i + L [ i ] NEW_LINE DEDENT DEDENT start = ( maxLPSCenterPosition - maxLPSLength ) / 2 NEW_LINE end = start + maxLPSLength - 1 NEW_LINE print " LPS ▁ of ▁ string ▁ is ▁ " + text + " ▁ : ▁ " , NEW_LINE print text [ start : end + 1 ] , NEW_LINE print   " NEW_LINE DEDENT " , NEW_LINE text1 = " babcbabcbaccba " NEW_LINE findLongestPalindromicString ( text1 ) NEW_LINE text2 = " abaaba " NEW_LINE findLongestPalindromicString ( text2 ) NEW_LINE text3 = " abababa " NEW_LINE findLongestPalindromicString ( text3 ) NEW_LINE text4 = " abcbabcbabcba " NEW_LINE findLongestPalindromicString ( text4 ) NEW_LINE text5 = " forgeeksskeegfor " NEW_LINE findLongestPalindromicString ( text5 ) NEW_LINE text6 = " caba " NEW_LINE findLongestPalindromicString ( text6 ) NEW_LINE text7 = " abacdfgdcaba " NEW_LINE findLongestPalindromicString ( text7 ) NEW_LINE text8 = " abacdfgdcabba " NEW_LINE findLongestPalindromicString ( text8 ) NEW_LINE text9 = " abacdedcaba " NEW_LINE findLongestPalindromicString ( text9 ) NEW_LINE