Table of Contents
Problem Statement
The problem “Palindrome Substring Queries” states that you are given a String and some queries. With those queries, you have to determine if the formed substring from that query is a palindrome or not.
Example
String str = "aaabbabbaaa"
Queries q[] = { {2, 3}, {2, 8},{5, 7}, {3, 7} }The Substring [2 3] is not a palindrome The Substring [2 8] is a palindrome The Substring [5 7] is not a palindrome The Substring [3 7] is a palindrome
Explanation: The substring [2,8] is a palindrome, and thus the result is YES. The substring is “abbabba”.
Approach
We have given a String and some queries, based on each query. We have to determine the substring so formed is a palindrome or not. Use String Hashing to solve this. We are going to use two arrays one for the original string and one for the reversed string. Then we will be storing the hash values of String. Here Hash Value can be different from one other. Suppose we are taking Hash Value for String[] and reverse Hash Value for reversed String. We will be taking prefix and suffix arrays.
Suppose we have String str: “aabbbababaaa”.
We will be storing the hash values of str as
Prefix[i] = str[0]+ str[1] *101 + str[2]*1012 + ……….+ str[i-1]*101*i-1 .
For each value of prefix [i]. We will have the following values:
Prefix[0]=0, Prefix[1]= 97 + 97 *101, ( 0+ ASCII value of a) Prefix[2]= 97 + 97 *101 + 98 *101^2 Prefix[3]= 97 + 97 *101 + 98 *101^2 + 98 *101^3 ( 0 + ASCII value of a’s and ASCII value of b). . . . Prefix [12]= 97 + 97 *101 + 98 *101^2 + 98 *101^3 +…… +97 *101^11 as length of String is 12.
So now, many of you are thinking why this is the way of storing Hash Values in such a way of this type. The answer is the way to search any given substring’s hash value by using a simple formula in the least time complexity.
Hash Value (Left, Right) = prefix[Right + 1] – prefix[Left].
Left and right can be substring starting point, If we want to find the hash value of string (2, 4)= “bbb”, then simply it will be:
prefix[5] – prefix[2]= 98 *1013 + 98 * 1014 + 98 * 1015.
This value will help in finding out the palindrome. Because the same we will do with the suffix array, but this time from last, let’s see how.
String str: “aabbbababaaa”.
suffix[i] = str[n-1]+ str[n-2] *101 + str[n-3]*1022 + ……….+ str[n-i]*101*i-1 . suffix[0]=0, suffix [1]= 97 + 97 *101, ( 0+ ASCII value of a) suffix [2]= 97 + 97 *101 + 97 *101^2, suffix [3]= 97 + 97 *101 + 97 *101^2 + 98 *101^3 ( 0 + ASCII value of a’s and ASCII value of b). . . . . suffix [11]= 97 + 97 *101 + 97 *101^2 + 98 *101^3 +…… +97 *101^10 as length of String is 11.
Now we can calculate the value of reverse Hash Value using:
Reverse Hash Value (Left, Right): Hash Value (Right, Left) = suffix [ n-Left] – suffix[n-Right-1].
Example
For example: String str: “aabbbababaaa”.
Reverse Hash Value: substring(2,4):
Reversing the value of “bbba” is “abbb”
Suffix[11-1] – suffix[11-4-1] = suffix[10]-suffix[6].
And now we have an equation to finding out the palindrome if it exists.
Now we are having two arrays as prefix and suffix, we have a relation between them.
(prefix[Right + 1] – prefix[Left]) = (suffix [n – Left] – suffix [n – Right- 1] )
(101Left) (101n – Right – 1)
Code
C++ code for Palindrome Substring Queries
#include<iostream>
using namespace std;
#define p 101
#define MOD 1000000007
struct Queries
{
int left, right;
};
bool CheckPalindrome(string str, int left, int right)
{
while (right > left)
if (str[left++] != str[right--])
return (false);
return (true);
}
unsigned long long int moduloPower(unsigned long long int base,unsigned long long int exponent)
{
if (exponent == 0)
return 1;
if (exponent == 1)
return base;
unsigned long long int temp = moduloPower(base, exponent / 2);
if (exponent % 2 == 0)
return (temp % MOD * temp % MOD) % MOD;
else
return (((temp % MOD * temp % MOD) % MOD)* base % MOD)% MOD;
}
unsigned long long int ModuloMultiplicativeInverse(unsigned long long int n)
{
return moduloPower(n, MOD - 2);
}
void HashPrefix( string str, int n, unsigned long long int prefix[], unsigned long long int powerArr[])
{
prefix[0] = 0;
prefix[1] = str[0];
for (int i = 2; i <= n; i++)
prefix[i] = (prefix[i - 1] % MOD + (str[i - 1] % MOD * powerArr[i - 1] % MOD) % MOD) % MOD;
return;
}
void HashSuffix( string str, int n, unsigned long long int suffix[], unsigned long long int powerArr[])
{
suffix[0] = 0;
suffix[1] = str[n - 1];
for (int i = n - 2, j = 2; i >= 0 && j <= n; i--, j++)
suffix[j] = (suffix[j - 1] % MOD+ (str[i] % MOD* powerArr[j - 1] % MOD)% MOD)% MOD;
return;
}
void GetQueryOutput(string str, Queries q[], int m, int n, unsigned long long int prefix[], unsigned long long int suffix[], unsigned long long int powerArr[])
{
for (int i = 0; i <= m - 1; i++)
{
int left = q[i].left;
int right = q[i].right;
unsigned long long HashValue= ((prefix[right + 1] - prefix[left] + MOD) % MOD* ModuloMultiplicativeInverse(powerArr[left]) % MOD)% MOD;
unsigned long long reverseHashValue= ((suffix[n - left] - suffix[n - right - 1] + MOD) % MOD* ModuloMultiplicativeInverse(powerArr[n - right - 1]) % MOD)% MOD;
if (HashValue == reverseHashValue)
{
if (CheckPalindrome(str, left, right) == true)
cout<<"The Substring ["<< left <<" "<<right<<"] is a palindrome\n";
else
cout<<"The Substring ["<< left <<" "<<right<<"] is a palindrome\n";
}
else
cout<<"The Substring ["<< left <<" "<<right<<"] is not a palindrome\n";
}
return;
}
void assginedPowers(unsigned long long int powerArr[], int n)
{
powerArr[0] = 1;
for (int i = 1; i <= n; i++)
powerArr[i] = (powerArr[i - 1] % MOD * p % MOD) % MOD;
return;
}
int main()
{
string str = "aaabbabbaaa";
int n = str.length();
unsigned long long int powerArr[n + 1];
assginedPowers(powerArr, n);
unsigned long long int prefix[n + 1];
unsigned long long int suffix[n + 1];
HashPrefix(str, n, prefix, powerArr);
HashSuffix(str, n, suffix, powerArr);
Queries q[] = { {2, 3}, {2, 8},{5, 7}, {3, 7} };
int m = sizeof(q) / sizeof(q[0]);
GetQueryOutput(str, q, m, n, prefix, suffix, powerArr);
return (0);
}
The Substring [2 3] is not a palindrome The Substring [2 8] is a palindrome The Substring [5 7] is not a palindrome The Substring [3 7] is a palindrome
Java code for Palindrome Substring Queries
public class PalindromeSubstringQuery
{
static int p = 101;
static int MOD = 1000000007;
public static class Queries
{
int left, right;
public Queries(int left, int right)
{
this.left = left;
this.right = right;
}
}
public static boolean CheckPalindrome(String str, int left, int right)
{
while (right > left)
{
if (str.charAt(left++) != str.charAt(right--))
return (false);
}
return (true);
}
public static int moduloPower(int base, int exponent)
{
if (exponent == 0)
{
return 1;
}
if (exponent == 1)
{
return base;
}
int temp = moduloPower(base, exponent / 2);
if (exponent % 2 == 0)
{
return (temp % MOD * temp % MOD) % MOD;
}
else
{
return (((temp % MOD * temp % MOD) % MOD) * base % MOD) % MOD;
}
}
public static int ModuloMultiplicativeInverse(int n)
{
return moduloPower(n, MOD - 2);
}
public static void HashPrefix(String str, int n,int prefix[], int powerArr[])
{
prefix[0] = 0;
prefix[1] = str.charAt(0);
for (int i = 2; i <= n; i++)
{
prefix[i] = (prefix[i - 1] % MOD+ (str.charAt(i - 1) % MOD * powerArr[i - 1] % MOD) % MOD) % MOD;
}
return;
}
public static void HashSuffix(String str, int n,int suffix[], int powerArr[])
{
suffix[0] = 0;
suffix[1] = str.charAt(n - 1);
for (int i = n - 2, j = 2; i >= 0 && j <= n; i--, j++)
{
suffix[j] = (suffix[j - 1] % MOD + (str.charAt(i) % MOD* powerArr[j - 1] % MOD) % MOD) % MOD;
}
return;
}
public static void GetQueryOutput( String str, Queries q[], int m, int n, int prefix[], int suffix[], int powerArr[])
{
for (int i = 0; i <= m - 1; i++)
{
int left = q[i].left;
int right = q[i].right;
long HashValue= ((prefix[right + 1] - prefix[left] + MOD) % MOD* ModuloMultiplicativeInverse(powerArr[left]) % MOD)% MOD;
long reverseHashValue= ((suffix[n - left] - suffix[n - right - 1] + MOD) % MOD* ModuloMultiplicativeInverse(powerArr[n - right - 1]) % MOD)% MOD;
if (HashValue == reverseHashValue)
{
if (CheckPalindrome(str, left, right) == true)
{
System.out.print("The Substring ["+left+" "+ right+"] is a palindrome\n");
}
else
{
System.out.print("The Substring ["+left+" "+ right+"] is not a palindrome\n");
}
}
else
{
System.out.print("The Substring ["+left+" "+ right+"] is not a palindrome\n");
}
}
return;
}
public static void assginedPowers(int powerArr[], int n)
{
powerArr[0] = 1;
for (int i = 1; i <= n; i++)
powerArr[i] = (powerArr[i - 1] % MOD * p % MOD) % MOD;
return;
}
public static void main(String[] args)
{
String str = "aaabbabbaaa";
int n = str.length();
int[] powerArr = new int[n + 1];
assginedPowers(powerArr, n);
int[] prefix = new int[n + 1];
int[] suffix = new int[n + 1];
HashPrefix(str, n, prefix, powerArr);
HashSuffix(str, n, suffix, powerArr);
Queries q[] = { new Queries(2, 3), new Queries(2, 8),new Queries(5, 7), new Queries(3, 7) };
int m = q.length;
GetQueryOutput(str, q, m, n, prefix, suffix, powerArr);
}
}
The Substring [2 3] is not a palindrome The Substring [2 8] is a palindrome The Substring [5 7] is not a palindrome The Substring [3 7] is a palindrome
Complexity Analysis
Time Complexity
O(N+Q) where “N” is the size of the string and “Q” is the number of queries to be performed. So, the algorithm has linear time complexity, as we answer each query in O(1) time.
Space Complexity
O(N) where “N” is the number of characters in the given string. Because we have stored hash values for the string. We used extra space.