Manacher’s Algorithm

Manacher's algorithm is used to find the longest palindromic substring in any string. It is required to solve sub-problems of some very hard problems. The problem statement it solves is: Given a string 's' with the length of 'n'. Find the longest palindromic substring in the given string. A string is a palindrome when it is equal to the reverse of itself.

Manacher's algorithm was invented by Manacher for listing all the palindromes that appear at the start of any given string, it was later observed that the same algorithm can be used to find the longest palindromic substring of any string in linear time.

Scope of the Article

• In this article, we will learn how to find the longest palindromic substring in any given string.
• We will discuss how to do it using the brute force approach and Manacher's algorithm.
• Every step in the algorithm will be explained thoroughly.
• Implementations will be explained using comments at each step.
• We will understand the Complexity Analysis of each implementation.

Takeaways

• Complexity of Manacher's algorithm
  • Time complexity – $O(N)$.

Brute Force Approach

The brute force / naive approach is slower than Manacher's algorithm, but it is a good stepping stone for understanding the problem and Manacher's algorithm. The Brute force approach is to check each substring of the given string whether the substring is a palindrome or not.

To implement the brute force approach, first, we will use a nested loop to get each substring, and then nest another loop to check whether that substring is a palindrome or not.

Implementation in C++ 17

// C++ solution for Longest Palindromic Substring (Brute Force)
#include <iostream>
using namespace std;

// A function to print a substring.
void printSubstring(string str, int left, int right){
    for (int i = left; i <= right; i++)
        cout << str[i];
}

// A function to get the longest palindromic substring 
// in the a given string using Brute Force Approach.
void longestPalSubstring(string str){
    // Getting length of the input string
    int n = str.size();

    // All substrings of length 1 are palindromes
    int maxLength = 1;

    int start = 0;

    // Checking all the substrings
    for (int i = 0; i < n; i++){
        for (int j = i; j < n; j++){
            int flag = 1;

            // Checking for a palindromic subtring
            for (int k = 0; k < (j - i + 1) / 2; k++)
                if (str[i + k] != str[j - k])
                    flag = 0;

            // If substring is palindromic
            if (flag && (j - i + 1) > maxLength){
                start = i;
                maxLength = j - i + 1;
            }
        }
    }

    // Printing the longest Palindromic substring
    cout << "The Longest Palindromic Substring is: ";
    printSubstring(str, start, start + maxLength - 1);
}

// Driver Code
int main(){
    string str = "daabddfddbegtd";
    longestPalSubstring(str);
    return 0;
}

Implementation in Python 3

# Python solution for Longest Palindromic Substring (Brute Force)

# A function to print a substring.
def printSubstring(str, left, right):
    for i in range(left, right + 1):
        print(str[i], end="")

# A function to get the longest palindromic substring in a
# given string using Brute Force Approach.
def longestPalSubstring(str):

    # Getting length of the input string
    n = len(str)

    # All substrings of length 1 are palindromes
    maxLength = 1
    start = 0

    # Checking all the substrings
    for i in range(n):
        for j in range(i, n):
            flag = 1

            # Checking for a palindromic subtring
            for k in range(0, ((j - i) // 2) + 1):
                if str[i + k] != str[j - k]:
                    flag = 0

            # If substring is palindromic
            if flag != 0 and (j - i + 1) > maxLength:
                start = i
                maxLength = j - i + 1

    # Printing the longest Palindromic substring
    print("The Longest Palindromic Substring is: ", end="")
    printSubstring(str, start, start + maxLength - 1)


# Driver Code
if __name__ == '__main__':
    my_string = "daabddfddbegtd"
    longestPalSubstring(my_string)

Implementation in Java 8

// Java solution for Longest Palindromic Substring (Brute Force)
import java.util.*;

class Manacher{

    // A function to print a substring.
    static void printSubstring(String str, int left, int right){
        for (int i = left; i <= right; i++)
            System.out.print(str.charAt(i));
    }

    // # A function to get the longest palindromic
    // substring in the a given string using Brute Force Approach
    static void longestPalSubstring(String str){
        // Getting length of the input string
        int n = str.length();

        // All substrings of length 1 are palindromes
        int maxLength = 1, start = 0;

        // Checking all the substrings
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int flag = 1;

                // Checking for a palindromic subtring
                for (int k = 0; k < (j - i + 1) / 2; k++)
                    if (str.charAt(i + k) != str.charAt(j - k))
                        flag = 0;

                // If substring is palindromic
                if (flag!=0 && (j - i + 1) > maxLength) {
                    start = i;
                    maxLength = j - i + 1;
                }
            }
        }

        // Printing the longest Palindromic substring
        System.out.print("The Longest Palindromic Substring is: ");
        printSubstring(str, start, start + maxLength - 1);
    }

    // Driver Code
    public static void main(String[] args) {
        String str = "daabddfddbegtd";
        longestPalSubstring(str);
    }
}

The output is the same for all of these (the implementation is the same, the difference is only of the programming languages).

Output

The Longest Palindromic Substring is: bddfddb

In the above examples, we are using the brute force approach to find the longest palindromic substring in the given string.
The printSubstring() function is used for printing a substring, longestPalSubstring() is used to print the longest palindromic substring.

Time Complexity:

$O(N^{3})$

In the brute force approach, three nested loops are used to find the longest palindromic substring, so the time complexity will be $O(N^{3})$.

Space Complexity

$O(1)$

No extra space is needed in this approach, so the space complexity will be $O(1)$.

Manacher’s algorithm

Manacher's algorithm is used to find the longest palindromic substring in any given string. This algorithm is faster than the brute force approach, as it exploits the idea of a palindrome happening inside another palindrome.

Manacher's algorithm is designed to find the palindromic substrings with odd lengths only. To use it for even lengths also, we tweak the input string by inserting the character “#” at the beginning and each alternate position after that (changing “abcaac” to “#a#b#c#a#a#c#“).

In the case of an odd length palindrome, the middle character will be a character of the original string, surrounded by “#“.

In the case of an even length palindrome, the middle character will be a “#” character.

Now we will learn each of its steps for a deeper understanding, which will help us in its implementation.

Steps of the Manacher’s Algorithm

Steps of the Manacher’s algorithm are as follows:

1. Create an array or a list ($sChars$) of length $strLen$ which is $2 * n + 3$ ($n$ being the length of the given string), to modify the given string.
2. Assign the first and last element of $sChars$ to be “@” and “$“, respectively.
3. Fill the blank spaces in $sChars$ by characters of the given string and “#” alternatively.
4. Declare variables

• Implicating maximum detected length of palindrome substring $maxLen = 0$
• Position from where to start searching $start = 0$
• Highest position of the extreme right character of all detected palindromes $maxRight = 0$
• Center of the detected palindrome $center = 0$.

1. Create an array or a list $p$ to record the width of each palindrome about their center, center being the corresponding characters in $sChars$.
2. Create a for loop iterating from $1$ to $strLen – 1$, with $i$ incrementing in each iteration.
3. In each iteration, check if $i < maxRight$, if yes, then assign minimum of $maxRight – i$ and $p[2 * center – i]$ to $p[i]$.
4. Nest a while loop inside the for loop, to count with width along the center, condition being, $sChars[i + p[i] + 1]$ is equal to $sChars[i – p[i] – 1]$, if yes, increment $p[i]$ by 1.
5. To update center, check if $i + p[i]$ is greater than $maxRight$, if yes, assign $center$ to be $1$, and $maxRight$ to be $i + p[i]$.
6. For updating the Maximum length detected, check if $p[i]$ is greater than $maxLen$, if yes, then assign $start$ to be $(i – p[i] – 1) / 2$, and $maxLen$ to be $p[i]$.
7. Come out of the for loop, and print the substring in the given string, starting from $start$ and ending at $start + maxLen – 1$.

Implementation of Manacher’s Algorithm

Now we will implement Manacher's algorithm in C++17, Java 8, and Python 3

Things to Note:

• $strLen$ is the length of the modified (after inserting extra characters) list/array.
• $sChars$ is the modified (after inserting extra characters) list/array.
• $maxLen$ is the length of the longest palindrome detected.
• $start$ is the position from which we have to search for a palindrome.
• $maxRight$ is the position of the rightmost character of a palindrome.
• $center$ is the center of a palindrome
• $p$ is the list/array of the width of palindromes about their center, center being the corresponding characters in $sChars$.

Implementation in C++ 17

// C++ solution for Longest Palindromic Substring (Manacher's Algorithm)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// A function to print a substring.
void printSubstring(string str, int left, int right){
    for (int i = left; i <= right; i++)
        cout << str[i];
}

// Implementation of Manacher's Algorithm
void longestPalSubstring(string s){
    /*
        If length of given string is n then its length after
        inserting n+1 "#", one "@", and one "$" will be
        (n) + (n+1) + (1) + (1) = 2n+3
    */
    int strLen = 2 * s.length() + 3;
    char* sChars = new char[strLen];

    /*
        Inserting special characters to ignore special cases
        at the beginning and end of the array
        "abc" -> @ # a # b # c # $
        "" -> @#$
        "a" -> @ # a # $
    */
    sChars[0] = '@';
    sChars[strLen - 1] = '$';
    int t = 1;

    for (char c : s){
        sChars[t++] = '#';
        sChars[t++] = c;
    }
    sChars[t] = '#';

    int maxLen = 0;
    int start = 0;
    int maxRight = 0;
    int center = 0;
    int* p = new int[strLen]; // i's radius, which doesn't include i

    for(int i = 1; i < strLen - 1; i++){
        if (i < maxRight){
            p[i] = min(maxRight - i, p[2 * center - i]);
        }

        // Expanding along the center
        while (sChars[i + p[i] + 1] == sChars[i - p[i] - 1]){
            p[i]++;
        }

        // Updating center and its bound
        if (i + p[i] > maxRight){
            center = i;
            maxRight = i + p[i];
        }

        // Updating ans
        if (p[i] > maxLen){
            start = (i - p[i] - 1) / 2;
            maxLen = p[i];
        }
    }

    // Printing the longest palindromic substring
    cout << "The Longest Palindromic Substring is: ";
    printSubstring(s, start, start + maxLen - 1);
}

// Driver Code
int main(){
    string str = "daabddfddbegtd";

    longestPalSubstring(str);
    return 0;
}

Implementation in Python 3

# Python solution for Longest Palindromic Substring (Manacher's Algorithm)

# A function to print a substring.
def printSubstring(str, left, right):
    for i in range(left, right + 1):
        print(str[i], end="")


# Implementation of Manacher's Algorithm
def longestPalSubstring(s):

    # If length of given string is n then its length after
    # inserting n+1 "#", one "@", and one "$" will be
    # (n) + (n+1) + (1) + (1) = 2n+3
    strLen = 2 * len(s) + 3
    sChars = [0]*strLen

    # Inserting special characters to ignore special cases
    # at the beginning and end of the array
    # "abc" -> @ # a # b # c # $
    # "" -> @#$
    # "a" -> @ # a # $
    sChars[0] = '@'
    sChars[strLen - 1] = '$'
    t = 1
    for i in s:
        sChars[t] = '#'
        t += 1
        sChars[t] = i
        t += 1

    sChars[t] = '#'

    maxLen = int(0)
    start = int(0)
    maxRight = int(0)
    center = int(0)
    p = [0] * strLen  # i's radius, which doesn't include i
    for i in range(1, strLen - 1):
        if i < maxRight:
            p[i] = min(maxRight - i, p[2 * center - i])

        # Expanding along the center
        while sChars[i + p[i] + 1] == sChars[i - p[i] - 1]:
            p[i] += 1

        # Updating center and its bound
        if i + p[i] > maxRight:
            center = i
            maxRight = i + p[i]

        # Updating ans
        if p[i] > maxLen:
            start = int((i - p[i] - 1) / 2)
            maxLen = p[i]

    # Printing the longest Palindromic substring
    print("The Longest Palindromic Substring is: ", end="")
    printSubstring(s, start, start + maxLen - 1)
    return


# Driver Code
if __name__ == '__main__':
    my_string = "daabddfddbegtd"
    longestPalSubstring(my_string)

Implementation in Java 8

// Java solution for Longest Palindromic Substring (Manacher's Algorithm)

class Manacher {

    // A function to print a substring.
    static void printSubstring(String str, int left, int right){
        for (int i = left; i <= right; i++)
            System.out.print(str.charAt(i));
    }

    // Implementation of Manacher's Algorithm
    public static void longestPalSubstring(String s) {
        /*
         If length of given string is n then its length after
         inserting n+1 "#", one "@", and one "$" will be
         (n) + (n+1) + (1) + (1) = 2n+3
        */
        int strLen = 2 * s.length() + 3;
        char[] sChars = new char[strLen];

        /*
         Inserting special characters to ignore special cases
         at the beginning and end of the array
         "abc" -> @ # a # b # c # $
         "" -> @#$
         "a" -> @ # a # $
        */
        sChars[0] = '@';
        sChars[strLen - 1] = '$';
        int t = 1;
        for (char c : s.toCharArray()) {
            sChars[t++] = '#';
            sChars[t++] = c;
        }
        sChars[t] = '#';

        int maxLen = 0;
        int start = 0;
        int maxRight = 0;
        int center = 0;
        int[] p = new int[strLen]; // i's radius, which doesn't include i
        for (int i = 1; i < strLen - 1; i++) {
            if (i < maxRight) {
                p[i] = Math.min(maxRight - i, p[2 * center - i]);
            }

            // Expanding along the center
            while (sChars[i + p[i] + 1] == sChars[i - p[i] - 1]) {
                p[i]++;
            }

            // Updating center and its bound
            if (i + p[i] > maxRight) {
                center = i;
                maxRight = i + p[i];
            }

            // Updating ans
            if (p[i] > maxLen) {
                start = (i - p[i] - 1) / 2;
                maxLen = p[i];
            }
        }

        // Printing the longest Palindromic substring
        System.out.print("The Longest Palindromic Substring is: ");
        printSubstring(s, start, start + maxLen - 1);
    }

    // Driver Code
    public static void main(String[] args){
        String str = "daabddfddbegtd";
        longestPalSubstring(str);
    }
}

The output is the same for all of these (the implementation is the same, the difference is only of the programming languages).

Output

The Longest Palindromic Substring is: bddfddb

In the above examples, we are using the Manacher’s algorithm to find the longest palindromic substring in the given string.
The printSubstring() function is used for printing a substring, longestPalSubstring() is used to print the longest palindromic substring.

Complexity Analysis of Manacher’s Algorithm

Analysing the Time and Spatial complexity of Manacher's algorithm ($N$ here is the number of characters inside the given string):

Time Complexity:

$O(N)$

At the first glance, it may seem that the algorithm has a $O(N^2)$ time complexity due to nested loops, but that’s not the case, a more careful analysis shows that the algorithm is linear and amortized.

Each successful comparison results in $maxRight$ moving one step forward, and it never reduces, therefore, the inner while loop gets executed at most $n$ times. Hence, the time complexity of Manacher's algorithm will be $O(N).$

Space Complexity:

$O(N)$

We need $O(n)$ space to create and form $p$ (palindrome width).

Boost Your Tech Profile! Join Our DSA Courses for Advanced Algorithmic Mastery. Enroll Now to Stand Out in the Coding Landscape!

Conclusion

• Manacher's Algorithm is used to find the longest palindrome substring in a given string.
• Finding the longest palindrome using the Brute Force algorithm is very slow, time complexity being $O(N^3)$.
• The given string needs to be modified by inserting a special character at every alternate position to work it with Manacher's algorithm in every case.
• Time Complexity of Manacher's algorithm is $O(N)$.
• Space Complexity of Manacher's algorithm is $O(N)$.