human
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"
Solution in Python:
assistant
#Here is code to manacher 's Algorithm and the other steps required.
 def findLongestPalindromicString ( text ) :
	N = len ( text )
	if N == 0 :
		return
	N = 2 * N + 1
	L = [ 0 ] * N
	L [ 0 ] = 0
	L [ 1 ] = 1
	C = 1
	R = 2
	i = 0
	iMirror = 0
	maxLPSLength = 0
	maxLPSCenterPosition = 0
	start = - 1
	end = - 1
	diff = - 1
	for i in xrange ( 2 , N ) :
		iMirror = 2 * C - i
		L [ i ] = 0
		diff = R - i
		if diff > 0 :
			L [ i ] = min ( L [ iMirror ] , diff )
		try :
			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 ] ) ) :
				L [ i ] += 1
		except Exception as e :
			pass
		if L [ i ] > maxLPSLength :
			maxLPSLength = L [ i ]
			maxLPSCenterPosition = i
		if i + L [ i ] > R :
			C = i
			R = i + L [ i ]
	start = ( maxLPSCenterPosition - maxLPSLength ) / 2
	end = start + maxLPSLength - 1
	print " LPS ▁ of ▁ string ▁ is ▁ " + text + " ▁ : ▁ " ,
	print text [ start : end + 1 ] ,
	print   "
" ,
text1 = " babcbabcbaccba "
findLongestPalindromicString ( text1 )
text2 = " abaaba "
findLongestPalindromicString ( text2 )
text3 = " abababa "
findLongestPalindromicString ( text3 )
text4 = " abcbabcbabcba "
findLongestPalindromicString ( text4 )
text5 = " forgeeksskeegfor "
findLongestPalindromicString ( text5 )
text6 = " caba "
findLongestPalindromicString ( text6 )
text7 = " abacdfgdcaba "
findLongestPalindromicString ( text7 )
text8 = " abacdfgdcabba "
findLongestPalindromicString ( text8 )
text9 = " abacdedcaba "
findLongestPalindromicString ( text9 )