Efficient Approach
We can make some critical observations regarding the palindromic substrings:

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:
 For a substring of odd length, the centre is the middle element. For e.g. The centre of “aba” is b.
 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.
 If we have a palindromic substring of length L centred at some position ‘i’, the substrings of length L2, L4, … 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[R1] 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].
 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.
 If i was inside the right endpoint, i.e., i < R, we will use the precalculated 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:

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.

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.

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.

Updating Palindrome Lengths: Update the array with the length of the palindrome at each index, based on the observed palindromes during the center expansion.

Track the Longest Palindrome: Maintain variables to keep track of the center and length of the longest palindrome found.

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++
#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 oddlength palindromes, but the evenlength palindromes of the original string are oddlength 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!