Python 12 lines clear O(n) Manacher algorithm with comments


  • 0

    Based on Manacher algorithm on Wiki and a brilliant article here http://articles.leetcode.com/longest-palindromic-substring-part-ii.

    class Solution(object):
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            # make it okay for both odd and even cases
            T = "^#" + "#".join(list(s)) + "#$"           
            n = len(T)
            P = [0] * n
            # C and R are center and right boundary of current farest palindrome
            C = R = 0                                     
            for i in range(1, n-1):
                P[i] = min(R-i, P[2*C-i]) if R > i else 0
                # check palindrome only for possible candidate, key idea why it's O(n)
                if P[i] + i >= R:                         
                    while T[i-1-P[i]] == T[i+1+P[i]]:     
                        P[i] += 1
                    # update C and R
                    C, R = i, i + P[i]                    
            L, C = max((x, j) for j, x in enumerate(P))
            return s[(C - L) >> 1 : (C + L) >> 1]
    

Log in to reply
 

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