Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Brute Force Approach
1.1.
Implementation
1.2.
C++
2.
Naive Approach
2.1.
Implementation
2.2.
C++
2.3.
Time Complexity
2.4.
Space Complexity
3.
Efficient Approach
4.
Manacher’s algorithm
5.
Problem
5.1.
Example 1
5.2.
Example 2
6.
Steps of the Manacher's Algorithm
6.1.
Implementation of Manacher’s Algorithm
6.2.
C++
6.3.
Handling centres between two indexes
7.
Frequently Asked Questions
7.1.
How does Manacher's algorithm work?
7.2.
What is Google Manacher's algorithm?
7.3.
What is a palindromic string?
7.4.
What is Manacher’s Algorithm?
8.
Conclusion
Last Updated: Mar 27, 2024
Easy

Manacher’s Algorithm

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Brute Force Approach

Manacher's Algorithm is used to find the longest palindromic substring in a given string. 

Manacher’s Algorithm

The brute force approach to find the longest palindromic substring involves checking every possible substring in the given string to determine if it is a palindrome. Here's how we can implement it in C++:

Implementation

  • C++

C++

#include <iostream>
#include <string>

using namespace std;

// Function to check if a string is a palindrome
bool isPalindrome(string str, int start, int end) {
while (start < end) {
if (str[start] != str[end])
return false;
start++;
end--;
}
return true;
}

// Function to find the longest palindromic substring using brute force approach
string longestPalindromicSubstring(string str) {
int n = str.length();
int maxLength = 0;
int start = 0;

// Check all substrings for palindromes
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (isPalindrome(str, i, j) && j - i + 1 > maxLength) {
maxLength = j - i + 1;
start = i;
}
}
}
return str.substr(start, maxLength);
}

int main() {
string str;
cout << "Enter a string: ";
cin >> str;
cout << "Longest palindromic substring is: " << longestPalindromicSubstring(str) << endl;
return 0;
}

Output

Enter a string: malayalam
Longest palindromic substring is: malayalam

 

Explanation

In this code, the isPalindrome function checks whether a substring of a given string is a palindrome. The longestPalindromicSubstring function iterates through all possible substrings of the input string and checks if each one is a palindrome. It returns the longest palindromic substring found. However, it's important to note that the brute force approach has a time complexity of O(n^3), which makes it inefficient for large strings.

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);
}

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).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

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

How does Manacher's algorithm work?

Manacher's algorithm efficiently finds the longest palindromic substring by expanding from each character to determine the length of palindromes centered at every position.

What is Google Manacher's algorithm?

Google's Manacher's algorithm likely refers to a variant or optimized version of Manacher's algorithm, tailored for specific applications or improvements in efficiency.

What is a palindromic string?

A palindromic string is a string that reads the same forwards and backward. For eg. “abba”, “hannah”, “bob” are palindromes, while “home”, “face” are not palindromes.

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. 

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 Coding Ninjas Studio. Do upvote our blog to help other ninjas grow. Happy Coding!

Previous article
Check if a Substring Exists, having Only Two Distinct Characters with The Frequency of One as Twice The Others
Next article
Count of Increasing Substrings in given String
Live masterclass