Manacher's Algorithm: Explanation, Code, Proof & CSES

Manacher's Algorithm: Explanation, Code, Proof & CSES

Hello everyone, today I'm going to explain a semi-niche algorithm called Manacher's algorithm. This algorithm can be used to find the longest palindrome in a string, count the number of palindromes of a certain length in a string, and more. It's also an introductory string algorithm that's relatively simple and can serve as a stepping stone to more complex algorithms. Let's get started!

Aim of the Algorithm

The aim of Manacher's algorithm is to calculate the length of the longest palindrome centered around each character in a string. For coding simplicity, instead of storing the actual lengths, we store the distance from the center of the palindrome to its boundary. For example, if the longest palindrome centered around a character 'B' is "CBC", the output array will store the number 2 for 'B' because the palindrome stretches out two characters in either direction.

Example:

Input String: "abbcbba"
Output Array: [1, 2, 3, 2, 1, 0, 0]

Naive Approach

A naive approach would involve initializing the length around each character to 1 and expanding outwards while checking that the expanding characters are equal. This naïve approach leads to an O(n²) worst-case runtime.

Example of Naive Approach:

Input String: "aaaa"
Output Array: [1, 2, 3, 4]

Optimized Approach with Manacher's Algorithm

Manacher's algorithm optimizes this process to run in O(n) time by leveraging previously computed palindromes and their properties.

1. Initialization:

   int len[n] = (0);
   int c = 0, r = 0; // c is the center of the current rightmost palindrome, r is its boundary
   

2. Processing Each Character:

   for (int i = 0; i < n; i++) (
       // Mirror index
       int mirror = 2 * c - i;
       // Initialize length
       if (r > i) len[i] = min(r - i, len[mirror]);
   
       // Center Expansion
       while (i + len[i] + 1 < n && i - len[i] - 1 >= 0 && s[i + len[i] + 1] == s[i - len[i] - 1]) {
           len[i]++;
       )
   
       // Update right boundary if needed
       if (i + len[i] > r) (
           c = i;
           r = i + len[i];
       )
   }
   

3. Using a Modified String:

   • Suppose the original string is "abba". Convert it to a format with boundary markers for easier handling: "abbab", you convert to "#a#b#b#a#".

4. Extracting the Longest Palindrome:

   • After constructing the len array, the maximum value indicates the length of the longest palindrome.

5. Final Implementation:

   string preprocess(const string& s) (
       string t = "#";
       for (char c : s) t += c + "#";
       return t;
   )
   
   string manacherLongestPalindrome(const string& s) (
       string t = preprocess(s);
       int n = t.size(), c = 0, r = 0;
       vector<int> len(n, 0);
   
       for (int i = 0; i < n; i++) {
           int mirror = 2 * c - i;
           if (r > i) len[i] = min(r - i, len[mirror]);
   
           while (i + len[i] + 1 < n && i - len[i] - 1 >= 0 && t[i + len[i] + 1] == t[i - len[i] - 1]) {
               len[i]++;
           )
           if (i + len[i] > r) (
               c = i;
               r = i + len[i];
           )
       }
   
       int maxLen = 0, centerIndex = 0;
       for (int i = 0; i < n; i++) (
           if (len[i] > maxLen) {
               maxLen = len[i];
               centerIndex = i;
           )
       }
   
       int start = (centerIndex - maxLen) / 2;
       return s.substr(start, maxLen);
   }
   

Proof of Linear Time Complexity

The algorithm runs in linear time because, for each character in the string, the while loop inside the main loop can increment the right boundary only once. The comparison of the palindrome boundaries results in constant time operations overall, leveraging the properties of the palindrome centered at the other side.

Testing with CSES Platform

After coding the algorithm, it was tested on the CSES "Longest Palindromic Substring" problem and functioned correctly. All test cases were resolved in 0.04 seconds, showing the efficiency of the implementation.

For further exploration, the Z-Algorithm, which has a similar optimization concept, will be discussed next time. The Z-Algorithm works on finding pattern matches efficiently by maintaining rightmost structures and leveraging their properties.

Keywords

• Manacher's Algorithm
• String Processing
• Palindromes
• Algorithm Optimization
• Linear Time Complexity

FAQ

1. What is Manacher's Algorithm used for?

   • It is used to find the longest palindrome in a string, count palindromes of a specific length, and more.

2. How does Manacher's Algorithm work?

   • It calculates the length of the longest palindrome centered at each character by utilizing memoized information about previous palindromes and leveraging symmetrical properties around a center.

3. Why is Manacher's Algorithm optimal for finding palindromes?

   • The algorithm runs in O(n) time because it optimizes the expansion check process by using previously computed palindromic lengths.

4. What kind of pre-processing is required for Manacher's Algorithm?

   • The input string is modified by inserting boundary markers to handle odd and even length palindromes uniformly.

5. Can Manacher's Algorithm be adapted for other languages?

   • Yes, the principles of the algorithm can be adapted to any programming language, maintaining its efficiency and correctness.