The Ultimate Guide to Manacher’s Algorithm

Palindromes are fascinating sequences that read the same backward as forward. In computer science, one popular problem is identifying the longest palindromic substring within a given string. While a brute-force approach may work, it often lacks efficiency, especially for long strings. That’s where Manacher’s Algorithm shines, offering a linear time complexity solution. Let’s dive deep into understanding Manacher’s Algorithm, why it’s so powerful, and how to implement it.

1. What is a Palindrome?

A palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward (ignoring spaces, punctuation, and capitalization). For example:

• madam is a palindrome.
• racecar is a palindrome.
• abcba is a palindrome.

When solving the “Longest Palindromic Substring” problem, we aim to find the longest segment in a string that forms a palindrome.

2. Naive Approach: Brute Force

The brute-force approach checks every possible substring and verifies if it’s a palindrome. This approach can take O(n³) time:

1. Iterate over each possible starting index.
2. Iterate over each possible ending index.
3. Check if the substring is a palindrome.

Due to its cubic complexity, this approach becomes impractical for long strings, motivating us to explore more efficient methods.

3. Why Use Manacher’s Algorithm?

Manacher’s Algorithm provides a method to solve the problem in O(n) time complexity. It leverages the symmetry properties of palindromes to optimize the search process. Unlike the brute-force approach, Manacher’s Algorithm doesn’t repeatedly check each substring for palindrome properties, saving computation time.

4. The Magic Behind Manacher’s Algorithm

Manacher’s Algorithm introduces a clever preprocessing step by inserting special characters (#) between each character and at the boundaries. This way:

• It avoids the need to differentiate between even and odd-length palindromes.
• Every palindrome is converted into an odd-length format.

Example:

Let’s say we have a string abba. With preprocessing, it becomes:

Original:  a  b  b  a
Modified:  #  a  #  b  #  b  #  a  #

5. Step-by-Step Explanation

Let’s break down Manacher’s Algorithm step by step:

1. Preprocessing: Modify the input string by adding special characters (#) to handle both odd and even-length palindromes uniformly.
2. Variables:
   • P[]: An array where P[i] stores the radius of the palindrome centered at i.
   • C: The center of the current palindrome.
   • R: The right edge of the current palindrome.
3. Expand Palindromes:
   • Iterate over the string. For each position i, determine the potential palindrome radius:
     1. Reflect the current index around C.
     2. Use previously computed values from the P[] array.
   • Attempt to expand the palindrome centered at i.
   • Update C and R if a longer palindrome is found.
4. Find the Longest Palindrome:
   • The maximum value in P[] gives the radius of the longest palindrome.
   • Use this information to extract the longest palindrome from the preprocessed string.

6. Code Implementation in Java

Here’s the Java code to implement Manacher’s Algorithm:

public class ManacherAlgorithm {

    public static String longestPalindromicSubstring(String s) {
        if (s == null || s.length() == 0) return "";

        // Preprocess the string
        String modifiedString = preprocess(s);
        int n = modifiedString.length();
        int[] P = new int[n];
        int C = 0, R = 0; // Center and Right edge of the palindrome

        // Apply Manacher's Algorithm
        for (int i = 0; i < n; i++) {
            int mirror = 2 * C - i; // Mirror index of i around center C

            // If within bounds, initialize P[i] using the mirror value
            if (R > i) {
                P[i] = Math.min(R - i, P[mirror]);
            }

            // Try expanding around the current center
            while (i + 1 + P[i] < n && i - 1 - P[i] >= 0 &&
                   modifiedString.charAt(i + 1 + P[i]) == modifiedString.charAt(i - 1 - P[i])) {
                P[i]++;
            }

            // Update C and R if the palindrome centered at i expands beyond R
            if (i + P[i] > R) {
                C = i;
                R = i + P[i];
            }
        }

        // Find the maximum length of palindrome in P[]
        int maxLength = 0;
        int centerIndex = 0;
        for (int i = 0; i < n; i++) {
            if (P[i] > maxLength) {
                maxLength = P[i];
                centerIndex = i;
            }
        }

        // Extract the longest palindrome from the original string
        int start = (centerIndex - maxLength) / 2; // Remove added characters
        return s.substring(start, start + maxLength);
    }

    // Helper function to preprocess the string
    private static String preprocess(String s) {
        StringBuilder modified = new StringBuilder("#");
        for (char c : s.toCharArray()) {
            modified.append(c).append("#");
        }
        return modified.toString();
    }

    public static void main(String[] args) {
        String input = "babad";
        System.out.println("Longest Palindromic Substring: " + longestPalindromicSubstring(input));
    }
}

7. Complexity Analysis

• Time Complexity: O(n) because each character in the modified string is processed a constant number of times.
• Space Complexity: O(n) due to the additional arrays and the modified string.

8. Conclusion

Manacher’s Algorithm is a powerful method for finding the longest palindromic substring efficiently. By cleverly preprocessing the string and utilizing symmetry properties, it reduces the problem’s complexity from cubic to linear time. Understanding this algorithm is essential for tackling problems that involve palindrome detection and is a classic example of how algorithmic optimizations can drastically improve performance.