Manacher Algorithm in Python O(n)


  • 0
    J
    class Solution(object):
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            s = '#' + '#'.join(s) + '#'
            RL = [0] * len(s)
            max_right = 0
            pos_ret,pos = 0,0
            len_ret,max_len = 0,0
            for i in range(len(s)):
                if i < max_right:
                    RL[i] = min(RL[2*pos-i], max_right-i)
                else:
                    RL[i] = 1            
                while i-RL[i] >=0 and i+RL[i]<len(s) and s[i-RL[i]] == s[i+RL[i]]:
                    RL[i] += 1            
                if RL[i] + i - 1 > max_right:
                    if RL[i] >= max_len:
                        pos_ret = i
                        len_ret = RL[i]
                    max_right = RL[i] + i - 1
                    pos = i                
                max_len = max(max_len, RL[i])
            t = s[pos_ret - len_ret + 1 : pos_ret + len_ret -1]
            return t.replace('#', '')
    

Log in to reply
 

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