Python 3 Script to Implement Manacher’s Algorithm to Find Palindrome String Full Project For Beginners

 

Welcome folks today in this blog post we will be implementing manacher's algorithm to find palindrome string. All the full source code of the application is shown below.

 

 

 

 

Get Started

 

 

 

In order to get started you need to make an app.py file and copy paste the following code

 

 

app.py

 

 

def manachers( S ):
    """
    O(n) algorithm to find longest palindrome substring
    :param S: string to process
    :return: longest palindrome
    """

    # Create a copy of array with sentinel chars in between and around
    # Also include space for starting and ending nodes
    T = [0] * (2 * (len(S)) + 3)

    # Fill odd indices with sentinel chars evens with real chars
    sen_char = "@"
    start_sen = "!"
    end_sen = "#"
    for i in range(len(T)):
        if i == 0:
            T[i] = start_sen
        elif i % 2 == 0 and i < len(T) - 1:
            s_index = (i - 1) // 2
            T[i] = S[s_index]
        elif i % 2 == 1 and i < len(T) - 1:
            T[i] = sen_char
        else:
            T[i] = end_sen

    # Also track the expand length around all indices
    P = [0] * len(T)

    # Track center of largest palin yet
    # and its right boundary
    center = right = 0

    # Track largest expansion length
    # and it index
    max_len = index = 0

    # Loop through word array to
    # update expand length around each index
    for i in range(1, len(T) - 1):

        # Check to see if new palin
        # around i lies within a bigger one
        # If so, copy expand length of its mirror
        mirror = 2 * center - i
        if i < right:
            P[i] = min(right - i, P[mirror])

        # Expand around new center
        # Update expand length at i as needed
        while T[i + P[i] + 1] == T[i - (P[i] + 1)]:
            P[i] += 1

        # If we breached previous right boundary
        # Make i the new center of the longest palin
        # and update right boundary
        if i + P[i] > right:
            right = i + P[i]
            center = i

        # Update max_len
        if P[i] > max_len:
            max_len = P[i]
            index = i

    t_arr = T[ index - max_len: index + max_len + 1 ]
    word_arr = [ c for c in t_arr if c != sen_char and c != start_sen and c != end_sen ]
    word = "".join(word_arr)

    return word

 

See also  Python 3 Topological Sorting Algorithm Script to Sort Number Array in Ascending or Descending Order Full Example Project For Beginners

 

Now if you execute the python script by typing the below command as shown below

 

 

python app.py

 

Leave a Reply