Manacher's Algorithm

longestPalindrome.py

def longestPalindrome(self, s):
    pt = 0
    temp = s
    while pt < len(temp):
        temp = temp[:pt]+"#"+temp[pt:]
        pt += 2
    temp = temp + "#"
    # the up-to-date longest center of palindrome
    center = 0
    # r is for range from the current longest center of palindrome
    r = 0
    register = [0]*len(temp)

    for i in range(1, len(temp)-1):
        mirror = 2*center-i
        if r > i:
            register[i] = min(r-i, register[mirror])
        else:
            register[i] = 0
        # expand from the current mid-point whenever possible
        while i+1+register[i]<len(temp) and temp[i+1+register[i]]==temp[i-1-register[i]]:
            register[i] += 1
        # check if the current range is the longest
        if i+register[i]>r:
            center = i
            r = i + register[i]
      radius = max(register)
    center = [i for i, j in enumerate(register) if j==radius][0]
    return s[(center-radius)/2:(center+radius+1)/2]