Manacher’s Algorithm

Naive Approach

To solve this problem, we can iterate over every substring of the given string and check if it is palindrome or not. We will first iterate over the left endpoint of the substring and then over the right endpoint. Then we again have to iterate over the current substring to check if it is palindrome or not.

Implementation

• C++

C++

// Function to find number of palindromic substrings
void solve(string s){
    int n = s.length();
    int ans = 0;

    // Iterating over the left endpoint
    for (int l=0; l<n; l++){

        // Iterating over the right endpoint
        for(int r=l; r<n; r++){
            int flag = 0;

            // Checking if it is palindromic substring
            for(int i=l; i<=r; i++){

                // If any character mismatches, we break
                if (s[i]!= s[r-i+l]){
                    flag = 1;
                    break;
                }
            }

            // If the substring is palindrome, increment ans
            if (!flag) ans++;
        }
    }

    // Printing the number of palindromic substrings
    cout<<ans<<endl;
}

// Driver Code
int main(){
    string s = "abaa";
    solve(s);
}

You can also try this code with Online C++ Compiler

Run Code

Output

6

Time Complexity

In the above code, we first iterated over the left endpoint, then over the right endpoint of the substring. This will take O(N ^ 2) time complexity. Again, we iterated from the left endpoint to the right endpoint to check if the substring was a palindrome or not. Therefore, the total time complexity of the above approach is O(N ^ 3).

Space Complexity

We have just used a few variables to calculate the answer; therefore, the space complexity of the above approach is O(1).

Efficient Approach

We can make some critical observations regarding the palindromic substrings:

1. There can be maximum O(N ^ 2) palindromic substrings, but the number of ‘centres’ of these substrings are at most 2 * N - 1. We define the centre of a substring as follows:
   1. For a substring of odd length, the centre is the middle element. For e.g. The centre of “aba” is b.
   2. For a substring of even length, the centre is the middle of the two adjacent characters in the middle of the substring. For e.g., if the string is “abba”, the centre will be the position between two adjacent b’s.
2. If we have a palindromic substring of length L centred at some position ‘i’, the substrings of length L-2, L-4, … that are centred at ‘i’ will also be palindromes.

Thus, if we can find the length of the longest palindromic substring for each centre, we can count the number of palindromic substrings at that index by dividing the count by 2. We will get the total number of palindromic substrings by adding this value for every centre.

Also check out - Substr C++

Manacher’s algorithm

This algorithm is used to find the length of the longest palindromic substring for each centre. First, we will discuss finding the number of palindromic substrings with odd lengths.

We maintain two endpoints L and R, for the rightmost found palindromic substring. That is, S[L+1], S[L+2], … S[R-1] is a palindrome with maximal R. We initialise L = 0 and R = 1. Let d1[i] be the array storing the length of the longest palindrome centred at ‘i’.

Now, let us assume that all the values of d1 till index ‘i’-1 are calculated, and we have to calculate d1[i].

1. If i is outside of the current right endpoint, i.e., i >= R, we increase d1[i] and check if the current rightmost substring S[i - d1[i]] to S[i + d1[i]] is a palindrome. We keep doing this until we find a mismatch or reach the string’s boundaries. We update our left and right endpoints accordingly.
2. If i was inside the right endpoint, i.e., i < R, we will use the pre-calculated values of d1[]. We will find the mirror position of ‘i’, i.e., the position j in the palindrome (L, R) that is symmetrical to i and assign d1[i] = d1[j]. 

Check out this problem - Check If A String Is Palindrome

Problem

You are given a string S of length N. Find the number of palindromic substrings in S.

Example 1

Input: S = “abac”

Output: 5

Explanation

The palindromic substrings for the given example are - “a”, “b”, “a”, “c”, “aba”. Therefore the answer is 5.

Example 2

Input: S = “abaa”

Output: 6

Explanation:

The palindromic substrings for the given example are - “a”, “b”, “a”, “a”, “aba”, “aa”.

Read about, kth largest element in an array, and Euclid GCD Algorithm

Steps of the Manacher's Algorithm

Manacher's Algorithm efficiently finds the longest palindromic substring in a given string. Here are the steps involved:

1. Preprocessing the String: Insert special characters between each character and at the beginning and end of the string. This step ensures that every palindrome, regardless of its odd or even length, will have a unique center character.
2. Initialize the Arrays: Initialize an array to store the length of the palindrome centered at each index and another array to track the maximum palindrome centered at each index.
3. Center Expansion: Iterate through the string, considering each character as a potential center of a palindrome. Expand around the center to check for palindromes of odd and even lengths simultaneously.
4. Updating Palindrome Lengths: Update the array with the length of the palindrome at each index, based on the observed palindromes during the center expansion.
5. Track the Longest Palindrome: Maintain variables to keep track of the center and length of the longest palindrome found.
6. Return the Longest Palindromic Substring: Once the algorithm completes, return the longest palindromic substring using the information gathered during the process. 

Implementation of Manacher’s Algorithm

• C++

C++

#include <bits/stdc++.h>
using namespace std;
#define ll long long

// Function to implement mancachers algorithm
vector<int> manacher(string s) {
    int n = s.size();
    s = "$" + s + "^";

    // d[i] = length of the longest palindromic substring centered at i
    vector<int> d(n + 2);
    int l = 0, r = -1;
    for(int i = 1; i <= n; i++) {
        d[i] = max(0, min(r - i, d[l + (r - i)]));
        while(s[i - d[i]] == s[i + d[i]]) {
            d[i]++;
        }
        if(i + d[i] > r) {
            l = i - d[i], r = i + d[i];
        }
    }
    return vector<int>(begin(d) + 1, end(d) - 1);
}

// Function to return maximum
void solve(string s){
    string t;

    // Appending # before and after each character
    for(auto c: s) {
        t += string("#") + c;
    }

    // Calling manacher on the modified string
    auto res = manacher(t + "#");

    /*
    l[i] will store the length of the longest palindromic substring
    centred at ith centre
    */
    vector<int> l = vector<int>(begin(res) + 1, end(res) - 1);

    // Counting the number of strings
    int cnt = 0;
    for(auto i: l){

        // Number of strings with center i = total/2
        cnt+= (i/2);
    }
    cout<<cnt<<endl;

}

// Driver Code
int main(){
    string s = "abaa";
    solve(s);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

6

Also read palindrome number in python.

Handling centres between two indexes

We have discussed the approach to find the length of the longest palindromic substring where the centre of the substring is equal to some index i. There can be cases when the centre of the substring is in the middle of two indexes, i.e., for even length substrings. We can either write another implementation of Manacher’s algorithm for even length substrings or modify the given substring such that we have to deal only with odd lengths. To do this, we can add additional character (say ‘#’) before and after each character of the string. Thus, if the string is “abaa”, the modified string will be “#a#b#a#a#”. 

The additional characters do not change the odd-length palindromes, but the even-length palindromes of the original string are odd-length palindromes of this new string.

Frequently Asked Questions

What is Manacher’s Algorithm?

Manacher’s algorithm is a string algorithm that is used to find the length of the longest palindromic substring for every ‘centre’. The centre is the middle element for odd length strings, and for even length strings, the centre lies between the two central characters. 

What is the time complexity of Manacher?

The time complexity of Manacher's algorithm is O(n), where n is the length of the input string.

What is Manacher's algorithm in C++?

Manacher's algorithm in C++ is used to find the longest palindromic substring in linear time (O(n)) by expanding around possible centers.

Conclusion

In this article, we have extensively discussed how to find the number of palindromic substrings in a string using mahacher’s algorithm and its implementation in C++. We hope that this blog has helped you enhance your knowledge of manacher’s algorithm and if you would like to learn more, check out our articles on Code360.