# Manacher’s algorithm solution in python

• The main idea is that find the longest palindrome substring `s[0:i]` starting from `s[0]`, and reverse the left part `s[i:]` to `s[i:][::-1]`, at last return `s[i:][::-1] + s`.

In Manacher’s algorithm, `s` is converted to a string `newS` splitted by `#`, for example `abc` -> `#a#b#c#`. And we know that `p[i]` is the radius of palindrome whose center is `newS[i]`, and `p[i] - 1` is the actually length of palindrome in `s`. So we only need to find the last `i` whose radius reaches the start of `newS`.

``````class Solution(object):
def shortestPalindrome(self, s):
original, s, n = s, '#{}#'.format('#'.join(list(s))),  2 * len(s) + 1
p, idx, maxReach = [0] * n, 0, 0

for i in xrange(n):
p[i] = min(maxReach - i, p[2 * idx - i]) if maxReach > i else 1

while i - p[i] >= 0 and i + p[i] < n and s[i - p[i]] == s[i + p[i]]:
p[i] += 1

if i + p[i] > maxReach:
idx = i
maxReach = i + p[i]

for i in xrange(n - 1, -1, -1):
if p[i] == i + 1:
return original[p[i] - 1:][::-1] + original
return original``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.