Solution Approach
Approach 1: Using Manacher’s Algorithm
Manacher’s algorithm is a string matching algorithm that works in linear time and is used to find the longest palindromic substring. The idea is that you take each point in the string as a midpoint and expand the string in both directions to find the longest palindromic substring. We can modify the manacher’s algorithm to count the number of different palindromes created from the string S by considering all the palindromes and not just the longest one. Let’s discuss the steps to implement modified Manacher’s algorithm to solve this problem.
The steps of implementation are:
-
Take the input string str
-
Declare a character array s and int array p. Set s[0] to ‘$’ and s[1] to ‘#’. Run a loop for i from 0 to length of string and store str[i] to s[i*2 +2] and ‘#’ to s[i*2+3]. Set the last index of s as ‘\0’. Use the memset function to initialise p array with 0. Initialise id and MaxL with 0.
-
Implement a for loop from i equal to 0 to the length of s. If p[id] + id is greater than i then update p[i] with the minimum value of p[2*id-i] and p[id] + id - i. Otherwise update p[i] by 1. While s[i + p[i]] is equal to s[i-p[i]] increment p[i]. Now if p[i] +1 > p[id] + id, update id with i. Add half of p[i] to MaxL.
- Print the answer which is the value stored in MaxL.
C++ Implementation
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
//defining important data structures
const int maxn = 1005;
char str[maxn];
char s[maxn*2];
int p[maxn*2];
int len;
//modified manacher’s algorithm
void Manacher(){
int i;
s[0] = '$';
s[1] = '#';
len = strlen(str);
//define s from str
for(i=0; i<len; i++) {
s[i*2 +2] = str[i];
s[i*2 +3] = '#';
}
len = i*2+2;
s[len] = '\0'; //To denote the end of string
int MaxL, id = 0;
MaxL =0;
//memset initialises p with 0 for all indices
memset(p,0,sizeof(p));
//i is the position of center element for current palindrome
for(int i=0; i<len; i++) {
if(p[id] + id > i)
p[i] = min(p[2*id-i], p[id] + id -i);
else
p[i] = 1;
while(s[i+p[i]] == s[i-p[i]])
p[i]++;
if(p[i] + i > p[id]+id) {
id = i;
}
MaxL += p[i]/2;
}
//print answer
cout<<MaxL<<endl;
}
int main(){
//Taking input
scanf("%s", str);
Manacher();
}
You can also try this code with Online C++ Compiler
Input
malayalam
Output
15
Complexities
Time Complexity
O(n), where n denotes the length of the input string
Reason: The total middle positions to check for palindromes are linear; hence the complexity of the algorithm is linear.
Space Complexity
O(n), where n denotes the length of the input string.
Reason: To store the input string and define s and p, we require linear space; therefore, the complexity is O(n).
Also check out - Substr C++ and Rabin Karp Algorithm
Approach 2: Using Suffix Tree
Another approach to solving this problem is using a suffix tree. A suffix tree is a data structure that is similar to trie, but it has all the suffixes of a text as its key. With the help of Ukkonen's Algorithm, we can construct the suffix tree in the worst-case time complexity of O(N).
The steps of implementation are:
-
Take the input string in s and store the length of s in variable len.
-
Initialise the suffix tree that we will use in solving this problem with the initTree function and set ans to 0.
-
Run a for loop over the input string and call the addLetter function for each letter of the input string. addLetter function takes the position of the current letter and modifies our suffix tree accordingly.
-
For each letter in the input string, increment the value of ans by the value of num of the tree[suff].
- Print the answer that is stored in ans variable.
C++ implementation
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
using namespace std;
#define MAX 1005
//node structure used to buildup the tree
struct Node
{
int next[26];
int len;
int sufflink;
int num;
}tree[MAX];
char s[MAX];
int num;
int suff;
//Function that adds the letter at the ,pos position by modifying the suffix tree
bool addLetter(int pos)
{
int cur=suff,curlen=0;
int let=s[pos]-'a';
while(1)
{
curlen=tree[cur].len;
if(pos-1-curlen>=0&&s[pos-1-curlen]==s[pos])
break;
cur=tree[cur].sufflink;
}
if(tree[cur].next[let])
{
suff=tree[cur].next[let];
return false;
}
num++;
suff=num;
tree[num].len=tree[cur].len+2;
tree[cur].next[let]=num;
if(tree[num].len==1)
{
tree[num].sufflink=2;
tree[num].num=1;
return true;
}
while(1)
{
cur=tree[cur].sufflink;
curlen=tree[cur].len;
if(pos-1-curlen>=0&&s[pos-1-curlen]==s[pos])
{
tree[num].sufflink=tree[cur].next[let];
break;
}
}
tree[num].num=1+tree[tree[num].sufflink].num;
return true;
}
//A function to initialize the suffix tree
void initTree()
{
num=2;suff=2;
tree[1].len=-1;tree[1].sufflink=1;
tree[2].len=0;tree[2].sufflink=1;
}
int main()
{
//Taking input
scanf("%s",s);
int len=strlen(s);
//Initializing the suffix tree
initTree();
long long int ans=0;
//Loop over the input string
for(int i=0;i<len;i++)
{
addLetter(i);
ans+=tree[suff].num;
}
//printing the output
printf("%d\n",ans);
return 0;
}
You can also try this code with Online C++ Compiler
Input
malayalam
Output
15
Complexities
Time Complexity
O(N logN), where N denotes the length of the input string
Reason: For running a for loop over the input string, e get the time complexity of O(N), then for searching in suffix tree we have the complexity of O(logN); Therefore the overall time complexity of this program is O(NlogN).
Space Complexity
O(n), where n denotes the length of the input string.
Reason: To store the input string we require linear space; therefore, the complexity is O(n).
Also see, Morris Traversal for Inorder.
You can also read about Palindrome Number in Python here.
FAQs
-
What is a palindromic string?
A string that is a palindrome is called a palindromic string. A palindrome is a word, number, verse or sentence that reads the same backward and forwards.
-
What is the use of the manacher’s algorithm?
Manacher’s algorithm is used to find the longest palindromic substring of a string in linear time. It can be modified to find solutions to the problems of counting palindromes.
-
What are the time and space complexity of the manacher’s algorithm?
The time complexity of the manacher’s algorithm is O(n) because the total middle points to check for palindromes is 2n+1. The space complexity is O(n).
-
What does the memset function in c++ do?
The memset function in c++ takes an object, a character, and a positive integer num in three arguments. It copies the character in the object num times. It is defined in <cstring> header file.
-
How many centre points are there in the manacher’s algorithm?
In the manacher’s algorithm, there are 2n+1 centres and not n centres. The reason is that for palindromes with the odd number of letters, there are n centres, and for an even number of letters, centres are between two characters.
-
Can a single character be a palindrome?
Yes, a single character is considered a palindrome because it reads the same forward and backwards.
Key Takeaways
This article discusses the most optimised solution of the problem Count Palindromes using Manacher’s Algorithm. We took advantage of mirror indexing and reused precomputed data when a palindrome exists inside another palindrome.
Check out this problem - Check If A String Is Palindrome
Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more?
Attempt our Online Mock Test Series on Coding Ninjas Studio now!
Happy Coding!
85+ registered