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.
In order to get started you need to make an
app.py file and copy paste the following code
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 =  * (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 =  * 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
Now if you execute the
python script by typing the below command as shown below