Manacher's Algorithm (Longest Palindromic Substring)

Welcome to our in-depth tutorial on Manacher's Algorithm, a powerful tool used to find the longest palindromic substring in a given string! This algorithm is a must-know for every programmer, as it can significantly speed up the process compared to the naive approach.

Let's start by understanding what a palindrome is. A palindrome is a word, phrase, number, or sequence that reads the same backward as forward. In the context of strings, a palindromic substring is a segment of the string that remains unchanged when its characters are reversed.

Here's a simple example:

python

# Example string
s = "racecar"

# Initializing a list to store the center and length of palindromes
p = [-1] * len(s)

💡 Pro Tip: The list p is crucial for Manacher's Algorithm. It will help us keep track of palindromes of all lengths and their centers.

Now, let's dive into the core of Manacher's Algorithm.

Radius Expansion

The main idea behind Manacher's Algorithm is to expand palindromes from their center (or radius) outwards. We do this by considering the longest palindrome found so far around each center and using it to find larger palindromes.

Here's how we implement it:

python

def manachers_algorithm(s):
    # Initializing center and length array
    p = [-1] * len(s)

    # Center of the current palindrome
    c = 0
    # Maximum palindrome length we've found so far
    r = 0

    # Iterate through the entire string
    for i in range(1, len(s)):
        # Use the minimum of c-r and i to determine the left boundary
        # of the current palindrome.
        left = max(0, c - r)

        # Use the minimum of r and i - 1 as the right boundary.
        right = min(r, i + 1)

        # Compare the characters at the left and right boundaries.
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1

        # Update the center and radius based on the new palindrome found.
        if right - left > r:
            c = i
            r = right - left

        # Update the length of the palindrome at the current position.
        p[i] = r - (c - i)

    return p

📝 Note: The manachers_algorithm function returns the p array, which stores the center and length of all palindromes found in the input string.

Now that we have the algorithm, let's put it into practice with a couple of examples.

Practical Examples

Example 1

python

s = "babad"
p = manachers_algorithm(s)
print(p)  # Output: [3, 2, 1, 0, -1, 0, 1, 2, 3]

In this example, the algorithm correctly finds the palindromes "a", "bab", "aba", and "babad".

Example 2

python

s = "racecar"
p = manachers_algorithm(s)
print(p)  # Output: [5, 2, 1, -1, 0, 0, 1, 0, -1, 0, 1, 2, 5]

In this example, the algorithm correctly finds the palindromes "a", "r", "race", "car", and "racecar".

🎯 Quiz: Given the following string s = "level". What is the longest palindromic substring found by Manacher's Algorithm, and what is its length?

That's all for our deep dive into Manacher's Algorithm! We hope you found this tutorial helpful and informative. Happy coding! 💻✨