Understanding Manacher’s Algorithm: Finding the Longest Palindromic Substring

In the world of programming, algorithms are the backbone of efficient problem-solving. Among these, Manacher’s Algorithm stands out for its ability to find the longest palindromic substring in linear time, O(N). This blog will delve into the intricacies of Manacher’s Algorithm, explaining its mechanics and providing a step-by-step guide to implement it in Java.

What is a Palindrome?

A palindrome is a sequence of characters that reads the same forward and backward. For example, words like “racecar” and “level” are palindromic. In the context of strings, identifying the longest palindromic substring is a common challenge in algorithms and data structures.

Why Use Manacher’s Algorithm?

While there are various methods to find palindromic substrings, many of them can be inefficient, particularly with larger input strings. Naive solutions typically involve checking all substrings, which results in a time complexity of O(N^2). Manacher’s Algorithm, however, achieves this in O(N) time complexity, making it significantly faster and more efficient.

How Does Manacher’s Algorithm Work?

Manacher’s Algorithm uses a clever technique to avoid redundant comparisons. It preprocesses the string by inserting special characters (like ‘#’) between each character and at the ends. This transformation allows the algorithm to treat even-length and odd-length palindromes uniformly.

Step-by-Step Breakdown of the Algorithm

Here’s a detailed breakdown of how Manacher’s Algorithm operates:

Preprocessing the String: Convert the original string into a new format that includes delimiters. For example, “abba” becomes “#a#b#b#a#”. This step helps in uniformly handling both even and odd length palindromes.
Initializing Variables: Create an array to hold the radius of palindromes centered at each character, and initialize variables to track the center and right edge of the rightmost palindrome found so far.
Expanding Around Centers: For each character in the preprocessed string, expand outwards to find the longest palindrome centered at that character. Use previously computed values to skip unnecessary checks.
Updating the Center and Right Edge: If the palindrome extends beyond the current right edge, update the center and right edge accordingly.
Extracting the Longest Palindrome: Once the loop completes, find the maximum value in the radius array to determine the longest palindromic substring.

Java Implementation of Manacher’s Algorithm

Now, let’s look at how to implement Manacher’s Algorithm in Java. Below is a complete code example to help you understand how it works:


public class ManachersAlgorithm {
    public static String longestPalindrome(String s) {
        // Preprocess the string
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            sb.append('#').append(c);
        }
        sb.append('#');
        String T = sb.toString();

        int n = T.length();
        int[] P = new int[n]; // Array to store the length of the palindrome at each center
        int center = 0, right = 0; // Current center and right edge of the rightmost palindrome

        for (int i = 0; i < n; i++) {
            int mirror = 2 * center - i; // Calculate the mirror index of the current index

            if (right > i) {
                P[i] = Math.min(right - i, P[mirror]); // Use the mirror's value if within bounds
            }

            // Attempt to expand the palindrome centered at i
            int a = i + (1 + P[i]), b = i - (1 + P[i]);
            while (a < n && b >= 0 && T.charAt(a) == T.charAt(b)) {
                P[i]++;
                a++;
                b--;
            }

            // Update center and right if the palindrome expanded beyond the right edge
            if (i + P[i] > right) {
                center = i;
                right = i + P[i];
            }
        }

        // Find the maximum element in P
        int maxLen = 0, maxCenter = 0;
        for (int i = 0; i < n; i++) {
            if (P[i] > maxLen) {
                maxLen = P[i];
                maxCenter = i;
            }
        }

        // Extract the longest palindromic substring
        int start = (maxCenter - maxLen) / 2; // Calculate the start index in the original string
        return s.substring(start, start + maxLen);
    }

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

This Java code implements Manacher’s Algorithm, efficiently finding the longest palindromic substring from the input string. The preprocessing step is crucial for handling various cases of palindromes uniformly.

Conclusion

Manacher’s Algorithm is a powerful tool in the realm of string manipulation, particularly for finding the longest palindromic substring efficiently. By understanding and implementing this algorithm, developers can solve related problems with enhanced performance.

For further learning, check out more coding videos on platforms like YouTube .

Additionally, if you’re looking to broaden your knowledge on data structures, explore playlists dedicated to Tree Data Structure and Graph Data Structure.

As you practice and implement these concepts, you’ll find yourself better equipped to tackle complex coding challenges and improve your programming skills.

Longest Palindromic Substring