## Python 3 Script to Implement Manacher’s Algorithm to Find Palindrome String Full Project For Beginners

Welcome folks today in this blog post we will be `implementing manacher's algorithm to find palindrome string`. All the full source code of the application is shown below.

# Get Started

In order to get started you need to make an `app.py` file and copy paste the following code

`app.py`

``````def manachers( S ):
"""
O(n) algorithm to find longest palindrome substring
:param S: string to process
:return: longest palindrome
"""

# Create a copy of array with sentinel chars in between and around
# Also include space for starting and ending nodes
T = [0] * (2 * (len(S)) + 3)

# Fill odd indices with sentinel chars evens with real chars
sen_char = "@"
start_sen = "!"
end_sen = "#"
for i in range(len(T)):
if i == 0:
T[i] = start_sen
elif i % 2 == 0 and i < len(T) - 1:
s_index = (i - 1) // 2
T[i] = S[s_index]
elif i % 2 == 1 and i < len(T) - 1:
T[i] = sen_char
else:
T[i] = end_sen

# Also track the expand length around all indices
P = [0] * len(T)

# Track center of largest palin yet
# and its right boundary
center = right = 0

# Track largest expansion length
# and it index
max_len = index = 0

# Loop through word array to
# update expand length around each index
for i in range(1, len(T) - 1):

# Check to see if new palin
# around i lies within a bigger one
# If so, copy expand length of its mirror
mirror = 2 * center - i
if i < right:
P[i] = min(right - i, P[mirror])

# Expand around new center
# Update expand length at i as needed
while T[i + P[i] + 1] == T[i - (P[i] + 1)]:
P[i] += 1

# If we breached previous right boundary
# Make i the new center of the longest palin
# and update right boundary
if i + P[i] > right:
right = i + P[i]
center = i

# Update max_len
if P[i] > max_len:
max_len = P[i]
index = i

t_arr = T[ index - max_len: index + max_len + 1 ]
word_arr = [ c for c in t_arr if c != sen_char and c != start_sen and c != end_sen ]
word = "".join(word_arr)

return word``````

See also  Python 3 Topological Sorting Algorithm Script to Sort Number Array in Ascending or Descending Order Full Example Project For Beginners

Now if you execute the `python script` by typing the below command as shown below

`python app.py`