Finding the Longest Palindromic Substring using Manacher's Algorithm in O(n) time complexity

LPS : Manacher's Algorithm.py

'''
There are 4 cases to handle
 * Case 1 : Right side palindrome is totally contained under current palindrome. In this case do not consider this as center.
 * Case 2 : Current palindrome is proper suffix of input. Terminate the loop in this case. No better palindrome will be found on right.
 * Case 3 : Right side palindrome is proper suffix and its corresponding left side palindrome is proper prefix of current palindrome. Make largest such point as next center.
 * Case 4 : Right side palindrome is proper suffix but its left corresponding palindrome is be beyond current palindrome. Do not consider this as center because it will not extend at all.
'''

def longest_palindromic_substring(string):
    # preprocess the string to allow for even length palindromes
    # abcd -> $a$b$c$d$
    new_string = '$' + '$'.join(string) + '$'
    # calculate new length of the processed palindrome -> 2n+1
    new_length = len(new_string)

    # create temporary list to keep track of the largest palindrome at every point
    p = [0 for i in range(new_length)]

    start = 0
    end = 0

    # i acts as the center
    i = 0
    while i < new_length:
        # expand around center i and see how big of a palindrome forms
        while start>0 and end<new_length-1 and new_string[start-1] == new_string[end+1]:
            start -= 1
            end += 1

        # update the value at p[i] with the length of the longest palindrome around center i
        p[i] = end-start+1

        # satisfies case 2
        # current palindrome is proper suffix of input and hence no need to proceed further
        if end == new_length-1:
            break

        # if even character ($) then new_center = end+1 otherwise for odd characters (not $) new_center = end
        new_center = end + (1 if i%2==0 else 0)

        # to find a better next center
        for c in range(i+1, end+1):
            # mirror of position c about the center i
            mirror = i - (c-i)
            
            # using the value of p[mirror] to find the palindrome size might give a length that exceeds the current palindrome about center i length
            # hence the minimum of the mirror value and palindrome formed till current end is put in the list
            p[c] = min(p[mirror], 2*(end-c)+1)

            # only proceed if case 3 condition is met
            # check is made to make sure c is not picked as new center for case 1 or case 4
            # break out of the loop and set new_center as c
            if (c + p[mirror]//2 == end):
                new_center = c
                break

        # make i as new_center
        # set end and start to atleast the value that should be matching based off of left side palindrome
        i = new_center
        end = i + p[i]//2
        start = i - p[i]//2

    # find the maximum length palindrome
    max_p = max(p)
    # calculate length of maximum palindrome
    p_length = max_p//2
    # index of the maximum length palindrome
    p_index = p.index(max_p)

    # the left and right indices of the palindrome
    l = p_index - p_length
    r = p_index + p_length

    # the palindrome in processed format
    palindrome = new_string[l:r+1]
    # removes all the special character $ from the palindrome
    palindrome = ''.join(char for char in palindrome if char != '$')

    return palindrome