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
```