Manacher's Algorithm for Longest Palindromic Substring

Understanding Manacher's Algorithm

Manacher's algorithm is a sophisticated and highly efficient algorithm that finds the longest palindromic substring in any given string in linear time, O(n). This is a significant improvement over the naive O(n^3) or dynamic programming O(n^2) approaches. The algorithm's cleverness lies in how it handles both even and odd-length palindromes and uses previously computed information to avoid redundant checks.

Example: Manacher's Algorithm Implementation

Here is a Python implementation of Manacher's algorithm. The key is to transform the string to handle all cases uniformly and then use a center and right boundary to optimize the expansion process.

def manacher_algorithm(s):
    if not s:
        return ""

    # 1. Transform S into T.
    # For example, S = "abba", T = "#a#b#b#a#".
    T = '#'.join('^{}$'.format(s))
    n = len(T)
    P = [0] * n
    C = R = 0

    for i in range(1, n - 1):
        # equals to i' = C - (i-C)
        i_mirror = 2 * C - i

        if R > i:
            P[i] = min(R - i, P[i_mirror])
        else:
            P[i] = 0

        # Attempt to expand palindrome centered at i
        while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
            P[i] += 1

        # If palindrome centered at i expand past R,
        # adjust center based on expanded palindrome.
        if i + P[i] > R:
            C = i
            R = i + P[i]

    # Find the maximum element in P.
    max_len = 0
    center_index = 0
    for i in range(1, n - 1):
        if P[i] > max_len:
            max_len = P[i]
            center_index = i

    # The original string's start index is (center_index - max_len) // 2
    start = (center_index - max_len) // 2
    return s[start:start + max_len]

# Example Usage
string1 = "babad"
print(f"Longest palindromic substring in '{string1}': {manacher_algorithm(string1)}") # Output: 'bab' or 'aba'

string2 = "cbbd"
print(f"Longest palindromic substring in '{string2}': {manacher_algorithm(string2)}") # Output: 'bb'

string3 = "abacdfgdcaba"
print(f"Longest palindromic substring in '{string3}': {manacher_algorithm(string3)}") # Output: 'aba'