Manacher’s algorithm solution in python


  • 1

    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

Log in to reply
 

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