Manacher's Algorithm

Introduction

Palindromes are sequences that read the same backward as forward. For example, "racecar" and "madam" are palindromes. Finding palindromic substrings in a string is a common problem in computer science, with applications in text processing, biological sequence analysis, and more.

Manacher's Algorithm, developed by Glenn Manacher in 1975, efficiently finds the longest palindromic substring in a string with linear time complexity O(n). This is a significant improvement over the naive O(n³) approach and even better than the O(n²) dynamic programming solution.

In this tutorial, we'll explore how Manacher's Algorithm works, implement it in code, and see it in action with practical examples.

The Problem

Before diving into the algorithm, let's clearly define our problem:

Given a string, find the longest palindromic substring within it.

For example:

• For the string "babad", the longest palindromic substring is "bab" or "aba" (both have length 3).
• For the string "cbbd", the longest palindromic substring is "bb" (length 2).

Naive Approach

The simplest approach would be to check every possible substring to see if it's a palindrome:

javascript

function isPalindrome(s) {
  const n = s.length;
  for (let i = 0; i < Math.floor(n / 2); i++) {
    if (s[i] !== s[n - 1 - i]) return false;
  }
  return true;
}

function naiveLongestPalindrome(s) {
  let maxLength = 0;
  let result = "";
  
  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      const substr = s.substring(i, j + 1);
      if (isPalindrome(substr) && substr.length > maxLength) {
        maxLength = substr.length;
        result = substr;
      }
    }
  }
  
  return result;
}

This approach has O(n³) time complexity - O(n²) for generating all substrings and O(n) for checking each substring.

Understanding Manacher's Algorithm

Manacher's algorithm uses two key insights to achieve linear time complexity:

1. Symmetry around a palindrome center: If we have a palindrome centered at position i, we can use the symmetry property to avoid redundant calculations.

2. Preprocessing the string: We insert special characters (like '#') between each character and at the ends to handle both odd and even-length palindromes uniformly.

Step 1: Preprocess the String

To handle both odd and even-length palindromes uniformly, we transform the input string by inserting special characters:

Original: "ababa"
Transformed: "#a#b#a#b#a#"

This way:

• Every character in the original string becomes a potential center for a palindrome.
• Both odd and even-length palindromes in the original string become odd-length palindromes in the transformed string.

Step 2: Build the Palindrome Radius Array

For each position in the transformed string, we calculate the "palindrome radius" - how far the palindrome extends on either side of the center.

Let's define:

• P[i]: The radius of the palindrome centered at position i
• C: The center of the rightmost palindrome we've examined
• R: The right boundary of the palindrome centered at C

The algorithm works as follows:

1. If i is outside the current palindrome (i > R), we start with P[i] = 0 and expand around i.

2. If i is inside the current palindrome (i <= R), we use the symmetry property. The mirror position of i with respect to C is j = 2*C - i. We set P[i] = min(P[j], R-i) and then try to expand further if possible.

Step 3: Find the Maximum Palindrome Length

Once we have the palindrome radius array, the longest palindromic substring has a center at the position with the maximum radius value.

Implementation of Manacher's Algorithm

Here's a complete implementation in JavaScript:

javascript

function manacher(s) {
  // Step 1: Preprocess the string
  const n = s.length;
  if (n === 0) return "";
  
  // Transform string by adding special characters
  const t = "#" + s.split("").join("#") + "#";
  const n2 = t.length;
  
  // Step 2: Build the palindrome radius array
  const P = new Array(n2).fill(0);
  let C = 0;  // Center of the rightmost palindrome
  let R = 0;  // Right boundary of the palindrome
  
  for (let i = 0; i < n2; i++) {
    // Mirror index on the left side of center C
    const mirror = 2 * C - i;
    
    // If i is within the rightmost palindrome, use the mirror value
    if (i < R) {
      P[i] = Math.min(R - i, P[mirror]);
    }
    
    // Expand around center i
    let a = i + (1 + P[i]);
    let b = i - (1 + P[i]);
    while (a < n2 && b >= 0 && t[a] === t[b]) {
      P[i]++;
      a++;
      b--;
    }
    
    // Update C and R if this palindrome extends beyond R
    if (i + P[i] > R) {
      C = i;
      R = i + P[i];
    }
  }
  
  // Step 3: Find the maximum palindrome length and its center
  let maxLen = 0;
  let centerIndex = 0;
  
  for (let i = 0; i < n2; i++) {
    if (P[i] > maxLen) {
      maxLen = P[i];
      centerIndex = i;
    }
  }
  
  // Extract the palindrome from the transformed string
  const start = Math.floor((centerIndex - maxLen) / 2);
  return s.substring(start, start + maxLen);
}

Let's trace through an example to see how this works.

Example: Step-by-Step Execution

Consider the string s = "babad":

1. Preprocess the string:

   Original: "babad"
   Transformed: "#b#a#b#a#d#"

2. Build the palindrome array P:

   Starting with P = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

   i = 0: P[0] = 0 (# has no matching character) i = 1: P[1] = 1 (#b# is a palindrome with radius 1) i = 2: P[2] = 0 (#a# only) i = 3: P[3] = 3 (#b#a#b# is a palindrome with radius 3) i = 4: P[4] = 0 i = 5: P[5] = 1 i = 6: P[6] = 0 i = 7: P[7] = 0 i = 8: P[8] = 0 i = 9: P[9] = 0 i = 10: P[10] = 0

   Final P = [0, 1, 0, 3, 0, 1, 0, 0, 0, 0, 0]

3. Find the maximum palindrome: The maximum radius is 3 at position 3. This corresponds to the palindrome "#b#a#b#" with radius 3. In the original string, this is "bab" starting from index 0.

So the longest palindromic substring is "bab".

Time and Space Complexity

• Time Complexity: O(n), where n is the length of the string. Each character is processed exactly once.
• Space Complexity: O(n) for storing the transformed string and the palindrome radius array.

Practical Applications

Manacher's algorithm has various practical applications:

1. Text Processing and Analysis

Palindrome detection is useful in text analysis, especially for languages that have palindromic structures or for finding word patterns.

javascript

function findAllPalindromes(text) {
  const words = text.toLowerCase().split(/\s+/);
  return words.filter(word => {
    const cleaned = word.replace(/[^a-z0-9]/g, '');
    return cleaned === cleaned.split('').reverse().join('') && cleaned.length > 1;
  });
}

const text = "Madam Arora teaches radar technology at noon.";
console.log(findAllPalindromes(text));  // ["madam", "arora", "radar", "noon"]

2. Bioinformatics

In DNA and protein sequence analysis, palindromic sequences often have biological significance.

javascript

function findDNAPalindromes(sequence, minLength = 4) {
  const results = [];
  
  // DNA complementary base pairs
  const complement = {
    'A': 'T', 'T': 'A', 'C': 'G', 'G': 'C'
  };
  
  for (let i = 0; i <= sequence.length - minLength; i++) {
    for (let j = i + minLength - 1; j < sequence.length; j++) {
      const subseq = sequence.substring(i, j + 1);
      
      // Check if it's a DNA palindrome (reverse complement)
      let isPalindrome = true;
      for (let k = 0; k < subseq.length; k++) {
        if (complement[subseq[k]] !== subseq[subseq.length - 1 - k]) {
          isPalindrome = false;
          break;
        }
      }
      
      if (isPalindrome) {
        results.push({
          start: i,
          end: j,
          sequence: subseq
        });
      }
    }
  }
  
  return results;
}

const dnaSequence = "GAATTC";
console.log(findDNAPalindromes(dnaSequence));  
// This is a palindromic sequence used by EcoRI restriction enzyme

3. Data Compression

Some compression algorithms use palindromes to identify repeating patterns in data, which can be represented more efficiently.

Summary

Manacher's Algorithm is a powerful technique that efficiently finds the longest palindromic substring in linear time. Here's what we've learned:

1. The algorithm uses a transformation to handle both odd and even-length palindromes uniformly.
2. It exploits the symmetry property of palindromes to avoid redundant calculations.
3. It has O(n) time complexity and O(n) space complexity.
4. The algorithm has practical applications in text processing, bioinformatics, and more.

To master Manacher's Algorithm, practice implementing it and solving related problems. The technique can be extended to solve more complex palindrome-related problems as well.

Exercises

1. Basic: Implement Manacher's Algorithm to find the longest palindromic substring in a given string.

2. Intermediate: Modify the algorithm to count all palindromic substrings in a string.

3. Advanced: Implement a version of the algorithm that returns all palindromic substrings with length greater than a given threshold.

4. Challenge: Use Manacher's Algorithm to find the shortest string that can be formed by adding characters to the beginning of the given string to make it a palindrome.

Additional Resources

• The original paper: Manacher, G. (1975). "A new linear-time on-line algorithm for finding the smallest initial palindrome of a string."
• "Longest Palindromic Substring" on LeetCode - Practice applying Manacher's Algorithm
• For visual learners, there are many YouTube videos that walk through the algorithm step by step with animations.

Remember, mastering algorithms like Manacher's is not just about memorizing the steps but understanding the intuition behind them. Practice implementing it from scratch until you can explain the process to someone else!