Given a string and several queries on the substrings of the given input string to check whether the substring is a palindrome or not.
Examples :
Suppose our input string is “abaaabaaaba” and the queries- [0, 10], [5, 8], [2, 5], [5, 9]
We have to tell that the substring having the starting and ending indices as above is a palindrome or not.
[0, 10] ? Substring is “abaaabaaaba” which is a palindrome.
[5, 8] ? Substring is “baaa” which is not a palindrome.
[2, 5] ? Substring is “aaab” which is not a palindrome.
[5, 9] ? Substring is “baaab” which is a palindrome.
Let us assume that there are Q such queries to be answered and N is the length of our input string. There are the following two ways to answer these queries.
Method 1 (Naive) :
One by one we go through all the substrings of the queries and check whether the substring under consideration is a palindrome or not.
Since there are Q queries and each query can take O(N) worse case time to answer, this method takes O(Q.N) time in the worst case. Although this is an in-place/space-efficient algorithm, still there is a more efficient method to do this.
C++
/* A C++ program to answer queries to check whetherthe substrings are palindrome or not */#include <bits/stdc++.h>using namespace std;// A function to check if a string str is palindrome// in the range L to Rbool isPalindrome(string& str, int L, int R){ // Keep comparing characters while they are same while (R > L) if (str[L++] != str[R--]) return (false); return (true);}/* Driver program to test above function */int main(){ string str = "abaaabaaaba"; int n = str.size(); vector<vector<int> > queries = { { 0, 10 }, { 5, 8 }, { 2, 5 }, { 5, 9 } }; for (auto q : queries) { bool result = isPalindrome(str, q[0], q[1]); if (result) cout << "The substring [" << q[0] << "," << q[1] << "] is a palindrome" << endl; else cout << "The substring [" << q[0] << "," << q[1] << "] is not palindrome" << endl; } return (0);}// This code is contributed by hkdass001 |
Java
import java.util.Arrays;import java.util.List;public class Main { // A function to check if a string str is palindrome // in the range L to R public static boolean isPalindrome(String str, int L, int R) { // Keep comparing characters while they are same while (R > L) { if (str.charAt(L++) != str.charAt(R--)) { return false; } } return true; } public static void main(String[] args) { String str = "abaaabaaaba"; int n = str.length(); List<List<Integer>> queries = Arrays.asList( Arrays.asList(0, 10), Arrays.asList(5, 8), Arrays.asList(2, 5), Arrays.asList(5, 9) ); for (List<Integer> q : queries) { boolean result = isPalindrome(str, q.get(0), q.get(1)); if (result) { System.out.println("The substring [" + q.get(0) + "," + q.get(1) + "] is a palindrome"); } else { System.out.println("The substring [" + q.get(0) + "," + q.get(1) + "] is not palindrome"); } } }} |
Python3
# A Python program to answer queries to check whether# the substrings are palindrome or notdef isPalindrome(string: str, L: int, R: int) -> bool: # Keep comparing characters while they are same while R > L: if str[L] != str[R]: return False L += 1 R -= 1 return True# Driver program to test above functionif __name__ == "__main__": str = "abaaabaaaba" n = len(str) queries = [[0, 10], [5, 8], [2, 5], [5, 9]] for q in queries: result = isPalindrome(str, q[0], q[1]) if result: print("The substring [{},{}] is a palindrome".format(q[0], q[1])) else: print("The substring [{},{}] is not palindrome".format(q[0], q[1]))# This code is contributed by Susobhan Akhuli |
C#
// C# program to answer queries to check whether the// substrings are palindrome or notusing System;using System.Collections.Generic;namespace PalindromeSubstring {class GFG { static void Main(string[] args) { // The string to check string str = "abaaabaaaba"; int n = str.Length; // A list of queries to check if the substrings are // palindromes List<List<int> > queries = new List<List<int> >{ new List<int>{ 0, 10 }, new List<int>{ 5, 8 }, new List<int>{ 2, 5 }, new List<int>{ 5, 9 } }; // Loop through each query foreach(var q in queries) { // Call the isPalindrome function to check if // the substring is a palindrome bool result = isPalindrome(str, q[0], q[1]); if (result) { // If the substring is a palindrome, print a // message Console.WriteLine("The substring [" + q[0] + "," + q[1] + "] is a palindrome"); } else { // If the substring is not a palindrome, // print a message Console.WriteLine("The substring [" + q[0] + "," + q[1] + "] is not palindrome"); } } } // A function to check if a string str is palindrome // in the range L to R static bool isPalindrome(string str, int L, int R) { // Keep comparing characters while they are the same while (R > L) { if (str[L++] != str[R--]) { return false; } } return true; }}}// This code is contributed by Susobhan Akhuli |
Javascript
// A function to check if a string str is palindrome// in the range L to Rfunction isPalindrome(str, L, R) { // Keep comparing characters while they are same while (R > L) { if (str[L++] !== str[R--]) { return false; } } return true;}/* Driver program to test above function */const str = "abaaabaaaba";const n = str.length;const queries = [ [0, 10], [5, 8], [2, 5], [5, 9],];for (let q of queries) { let result = isPalindrome(str, q[0], q[1]); if (result) { console.log(`The substring [${q[0]},${q[1]}] is a palindrome`); } else { console.log(`The substring [${q[0]},${q[1]}] is not palindrome`); }}// This code is contributed by unstoppablepandu. |
Output
The substring [0,10] is a palindrome The substring [5,8] is not palindrome The substring [2,5] is not palindrome The substring [5,9] is a palindrome
Time Complexity: O(N*Q)
Auxiliary Space: O(1)
Method 2 (Cumulative Hash):
The idea is similar to Rabin Karp string matching. We use string hashing. What we do is that we calculate cumulative hash values of the string in the original string as well as the reversed string in two arrays- prefix[] and suffix[].
How to calculate the cumulative hash values?
Suppose our string is str[], then the cumulative hash function to fill our prefix[] array used is-
prefix[0] = 0
prefix[i] = str[0] + str[1] * 101 + str[2] * 1012 + …… + str[i-1] * 101i-1
For example, take the string- “abaaabxyaba”
prefix[0] = 0
prefix[1] = 97 (ASCII Value of ‘a’ is 97)
prefix[2] = 97 + 98 * 101
prefix[3] = 97 + 98 * 101 + 97 * 1012
………………………
………………………
prefix[11] = 97 + 98 * 101 + 97 * 1012 + ……..+ 97 * 10110
Now the reason to store in that way is that we can easily find the hash value of any substring in O(1) time using-
hash(L, R) = prefix[R+1] – prefix[L]
For example, hash (1, 5) = hash (“baaab”) = prefix[6] – prefix[1] = 98 * 101 + 97 * 1012 + 97 * 1013 + 97 * 1014 + 98 * 1015 = 1040184646587 [We will use this weird value later to explain what’s happening].
Similar to this we will fill our suffix[] array as-
suffix[0] = 0
suffix[i] = str[n-1] + str[n-2] * 1011 + str[n-3] * 1012 + …… + str[n-i] * 101i-1
For example, take the string- “abaaabxyaba”
suffix[0] = 0
suffix[1] = 97 (ASCII Value of ‘a’ is 97)
suffix[2] = 97 + 98 * 101
suffix[3] = 97 + 98 * 101 + 97 * 1012
………………………
………………………
suffix[11] = 97 + 98 * 101 + 97 * 1012 + ……..+ 97 * 10110
Now the reason to store in that way is that we can easily find the reverse hash value of any substring in O(1) time usingreverse_hash(L, R) = hash (R, L) = suffix[n-L] – suffix[n-R-1]where n = length of string.
For “abaaabxyaba”, n = 11
reverse_hash(1, 5) = reverse_hash(“baaab”) = hash(“baaab”) [Reversing “baaab” gives “baaab”]
hash(“baaab”) = suffix[11-1] – suffix[11-5-1] = suffix[10] – suffix[5] = 98 * 1015 + 97 * 1016 + 97 * 1017 + 97 * 1018 + 98 * 1019 = 108242031437886501387
Now there doesn’t seem to be any relationship between these two weird integers – 1040184646587 and 108242031437886501387
Think again. Is there any relation between these two massive integers ?
Yes, there is and this observation is the core of this program/article.
1040184646587 * 1014 = 108242031437886501387
Try thinking about this and you will find that any substring starting at index- L and ending at index- R (both inclusive) will be a palindrome if
(prefix[R + 1] – prefix[L]) / (101L) = (suffix [n – L] – suffix [n – R- 1] ) / (101n – R – 1)
The rest part is just implementation.
The function computerPowers() in the program computes the powers of 101 using dynamic programming.Overflow Issues:
As, we can see that the hash values and the reverse hash values can become huge for even the small strings of length – 8. Since C and C++ doesn’t provide support for such large numbers, so it will cause overflows. To avoid this we will take modulo of a prime (a prime number is chosen for some specific mathematical reasons). We choose the biggest possible prime which fits in an integer value. The best such value is 1000000007. Hence all the operations are done modulo 1000000007.
However, Java and Python has no such issues and can be implemented without the modulo operator.
The fundamental modulo operations which are used extensively in the program are listed below.
1) Addition-
(a + b) %M = (a %M + b % M) % M
(a + b + c) % M = (a % M + b % M + c % M) % M
(a + b + c + d) % M = (a % M + b % M + c % M+ d% M) % M
…. ….. ….. ……
…. ….. ….. ……
2) Multiplication-
(a * b) % M = (a * b) % M
(a * b * c) % M = ((a * b) % M * c % M) % M
(a * b * c * d) % M = ((((a * b) % M * c) % M) * d) % M
…. ….. ….. ……
…. ….. ….. ……This property is used by modPow() function which computes power of a number modulo M
3) Mixture of addition and multiplication-
(a * x + b * y + c) % M = ( (a * x) % M +(b * y) % M+ c % M ) % M
4) Subtraction-
(a – b) % M = (a % M – b % M + M) % M [Correct]
(a – b) % M = (a % M – b % M) % M [Wrong]
5) Division-
(a / b) % M = (a * MMI(b)) % M
Where MMI() is a function to calculate Modulo Multiplicative Inverse. In our program this is implemented by the function- findMMI().
Implementation of the above approach:
C++
/* A C++ program to answer queries to check whether the substrings are palindrome or not efficiently */#include <bits/stdc++.h>using namespace std;#define p 101#define MOD 1000000007// Structure to represent a query. A query consists// of (L, R) and we have to answer whether the substring// from index-L to R is a palindrome or notstruct Query { int L, R;};// A function to check if a string str is palindrome// in the range L to Rbool isPalindrome(string str, int L, int R){ // Keep comparing characters while they are same while (R > L) if (str[L++] != str[R--]) return (false); return (true);}// A Function to find pow (base, exponent) % MOD// in log (exponent) timeunsigned long long int modPow( 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 = modPow(base, exponent / 2); if (exponent % 2 == 0) return (temp % MOD * temp % MOD) % MOD; else return (((temp % MOD * temp % MOD) % MOD) * base % MOD) % MOD;}// A Function to calculate Modulo Multiplicative Inverse of 'n'unsigned long long int findMMI(unsigned long long int n){ return modPow(n, MOD - 2);}// A Function to calculate the prefix hashvoid computePrefixHash( string str, int n, unsigned long long int prefix[], unsigned long long int power[]){ prefix[0] = 0; prefix[1] = str[0]; for (int i = 2; i <= n; i++) prefix[i] = (prefix[i - 1] % MOD + (str[i - 1] % MOD * power[i - 1] % MOD) % MOD) % MOD; return;}// A Function to calculate the suffix hash// Suffix hash is nothing but the prefix hash of// the reversed stringvoid computeSuffixHash( string str, int n, unsigned long long int suffix[], unsigned long long int power[]){ 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 * power[j - 1] % MOD) % MOD) % MOD; return;}// A Function to answer the Queriesvoid queryResults(string str, Query q[], int m, int n, unsigned long long int prefix[], unsigned long long int suffix[], unsigned long long int power[]){ for (int i = 0; i <= m - 1; i++) { int L = q[i].L; int R = q[i].R; // Hash Value of Substring [L, R] unsigned long long hash_LR = ((prefix[R + 1] - prefix[L] + MOD) % MOD * findMMI(power[L]) % MOD) % MOD; // Reverse Hash Value of Substring [L, R] unsigned long long reverse_hash_LR = ((suffix[n - L] - suffix[n - R - 1] + MOD) % MOD * findMMI(power[n - R - 1]) % MOD) % MOD; // If both are equal then // the substring is a palindrome if (hash_LR == reverse_hash_LR) { if (isPalindrome(str, L, R) == true) printf("The Substring [%d %d] is a " "palindrome\n", L, R); else printf("The Substring [%d %d] is not a " "palindrome\n", L, R); } else printf("The Substring [%d %d] is not a " "palindrome\n", L, R); } return;}// A Dynamic Programming Based Approach to compute the// powers of 101void computePowers(unsigned long long int power[], int n){ // 101^0 = 1 power[0] = 1; for (int i = 1; i <= n; i++) power[i] = (power[i - 1] % MOD * p % MOD) % MOD; return;}/* Driver program to test above function */int main(){ string str = "abaaabaaaba"; int n = str.length(); // A Table to store the powers of 101 unsigned long long int power[n + 1]; computePowers(power, n); // Arrays to hold prefix and suffix hash values unsigned long long int prefix[n + 1], suffix[n + 1]; // Compute Prefix Hash and Suffix Hash Arrays computePrefixHash(str, n, prefix, power); computeSuffixHash(str, n, suffix, power); Query q[] = { { 0, 10 }, { 5, 8 }, { 2, 5 }, { 5, 9 } }; int m = sizeof(q) / sizeof(q[0]); queryResults(str, q, m, n, prefix, suffix, power); return (0);} |
Java
/* A Java program to answer queries to check whether the substrings are palindrome or not efficiently */public class GFG { static int p = 101; static int MOD = 1000000007; // Structure to represent a query. A query consists // of (L, R) and we have to answer whether the substring // from index-L to R is a palindrome or not static class Query { int L, R; public Query(int L, int R) { this.L = L; this.R = R; } }; // A function to check if a string str is palindrome // in the range L to R static boolean isPalindrome(String str, int L, int R) { // Keep comparing characters while they are same while (R > L) { if (str.charAt(L++) != str.charAt(R--)) { return (false); } } return (true); } // A Function to find pow (base, exponent) % MOD // in log (exponent) time static int modPow(int base, int exponent) { if (exponent == 0) { return 1; } if (exponent == 1) { return base; } int temp = modPow(base, exponent / 2); if (exponent % 2 == 0) { return (temp % MOD * temp % MOD) % MOD; } else { return (((temp % MOD * temp % MOD) % MOD) * base % MOD) % MOD; } } // A Function to calculate // Modulo Multiplicative Inverse of 'n' static int findMMI(int n) { return modPow(n, MOD - 2); } // A Function to calculate the prefix hash static void computePrefixHash(String str, int n, int prefix[], int power[]) { 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 * power[i - 1] % MOD) % MOD) % MOD; } return; } // A Function to calculate the suffix hash // Suffix hash is nothing but the prefix hash of // the reversed string static void computeSuffixHash(String str, int n, int suffix[], int power[]) { 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 * power[j - 1] % MOD) % MOD) % MOD; } return; } // A Function to answer the Queries static void queryResults( String str, Query q[], int m, int n, int prefix[], int suffix[], int power[]) { for (int i = 0; i <= m - 1; i++) { int L = q[i].L; int R = q[i].R; // Hash Value of Substring [L, R] long hash_LR = ((prefix[R + 1] - prefix[L] + MOD) % MOD * findMMI(power[L]) % MOD) % MOD; // Reverse Hash Value of Substring [L, R] long reverse_hash_LR = ((suffix[n - L] - suffix[n - R - 1] + MOD) % MOD * findMMI(power[n - R - 1]) % MOD) % MOD; // If both are equal then the substring is a palindrome if (hash_LR == reverse_hash_LR) { if (isPalindrome(str, L, R) == true) { System.out.printf("The Substring [%d %d] is a " + "palindrome\n", L, R); } else { System.out.printf("The Substring [%d %d] is not a " + "palindrome\n", L, R); } } else { System.out.printf("The Substring [%d %d] is not a " + "palindrome\n", L, R); } } return; } // A Dynamic Programming Based Approach to compute the // powers of 101 static void computePowers(int power[], int n) { // 101^0 = 1 power[0] = 1; for (int i = 1; i <= n; i++) { power[i] = (power[i - 1] % MOD * p % MOD) % MOD; } return; } /* Driver code */ public static void main(String[] args) { String str = "abaaabaaaba"; int n = str.length(); // A Table to store the powers of 101 int[] power = new int[n + 1]; computePowers(power, n); // Arrays to hold prefix and suffix hash values int[] prefix = new int[n + 1]; int[] suffix = new int[n + 1]; // Compute Prefix Hash and Suffix Hash Arrays computePrefixHash(str, n, prefix, power); computeSuffixHash(str, n, suffix, power); Query q[] = { new Query(0, 10), new Query(5, 8), new Query(2, 5), new Query(5, 9) }; int m = q.length; queryResults(str, q, m, n, prefix, suffix, power); }}// This code is contributed by Princi Singh |
Python3
# A Python program to answer queries to check whether# the substrings are palindrome or not efficiently# define constantsp = 101MOD = 1000000007# Structure to represent a query. A query consists# of (L, R) and we have to answer whether the substring# from index-L to R is a palindrome or notclass Query: def __init__(self, L, R): self.L = L self.R = R# A function to check if a string strng is palindrome# in the range L to Rdef is_palindrome(strng, L, R): # Keep comparing characters while they are same while R > L: if strng[L] != strng[R]: return False L += 1 R -= 1 return True# A Function to find pow (base, exponent) % MOD# in log (exponent) timedef mod_pow(base, exponent): if exponent == 0: return 1 if exponent == 1: return base temp = mod_pow(base, exponent // 2) if exponent % 2 == 0: return (temp % MOD * temp % MOD) % MOD else: return (((temp % MOD * temp % MOD) % MOD) * base % MOD) % MOD# A Function to calculate Modulo Multiplicative Inverse of 'n'def find_MMI(n): return mod_pow(n, MOD - 2)# A Function to calculate the prefix hashdef compute_prefix_hash(strng, n, prefix, power): prefix[0] = 0 prefix[1] = ord(strng[0]) for i in range(2, n + 1): prefix[i] = (prefix[i - 1] % MOD + (ord(strng[i - 1]) % MOD * power[i - 1] % MOD) % MOD) % MOD return# A Function to calculate the suffix hash# Suffix hash is nothing but the prefix hash of# the reversed stringdef compute_suffix_hash(strng, n, suffix, power): suffix[0] = 0 suffix[1] = ord(strng[n - 1]) for i in range(n - 2, -1, -1): j = n - i suffix[j] = (suffix[j - 1] % MOD + (ord(strng[i]) % MOD * power[j - 1] % MOD) % MOD) % MOD return# A Function to answer the Queriesdef query_results(strng, q, m, n, prefix, suffix, power): for i in range(m): L = q[i].L R = q[i].R # Hash Value of Substring [L, R] hash_LR = ((prefix[R + 1] - prefix[L] + MOD) % MOD * find_MMI(power[L]) % MOD) % MOD # Reverse Hash Value of Substring [L, R] reverse_hash_LR = ((suffix[n - L] - suffix[n - R - 1] + MOD) % MOD * find_MMI(power[n - R - 1]) % MOD) % MOD # If both are equal then # the substring is a palindrome if hash_LR == reverse_hash_LR: if is_palindrome(strng, L, R) == True: print("The Substring [%d %d] is a palindrome" % (L, R)) else: print("The Substring [%d %d] is not a palindrome" % (L, R)) else: print("The Substring [%d %d] is not a palindrome" % (L, R)) return# A Dynamic Programming Based Approach to compute the# powers of 101def compute_powers(power, n): # 101^0 = 1 power[0] = 1 for i in range(1, n + 1): power[i] = (power[i - 1] % MOD * p % MOD) % MOD return# Driver program to test above functionif __name__ == '__main__': strng = "abaaabaaaba" n = len(strng) # A Table to store the powers of 101 power = [0] * (n + 1) compute_powers(power, n) # Arrays to hold prefix and suffix hash values prefix = [0] * (n + 1) suffix = [0] * (n + 1) # Compute Prefix Hash and Suffix Hash Arrays compute_prefix_hash(strng, n, prefix, power) compute_suffix_hash(strng, n, suffix, power) q = [Query(0, 10), Query(5, 8), Query(2, 5), Query(5, 9)] m = len(q) query_results(strng, q, m, n, prefix, suffix, power)# This code is contributed by Susobhan Akhuli |
C#
/* A C# program to answer queries to check whether the substrings are palindrome or not efficiently */using System;class GFG { static int p = 101; static int MOD = 1000000007; // Structure to represent a query. A query consists // of (L, R) and we have to answer whether the substring // from index-L to R is a palindrome or not public class Query { public int L, R; public Query(int L, int R) { this.L = L; this.R = R; } }; // A function to check if a string str is palindrome // in the range L to R static Boolean isPalindrome(String str, int L, int R) { // Keep comparing characters while they are same while (R > L) { if (str[L++] != str[R--]) { return (false); } } return (true); } // A Function to find pow (base, exponent) % MOD // in log (exponent) time static int modPow(int Base, int exponent) { if (exponent == 0) { return 1; } if (exponent == 1) { return Base; } int temp = modPow(Base, exponent / 2); if (exponent % 2 == 0) { return (temp % MOD * temp % MOD) % MOD; } else { return (((temp % MOD * temp % MOD) % MOD) * Base % MOD) % MOD; } } // A Function to calculate Modulo Multiplicative Inverse of 'n' static int findMMI(int n) { return modPow(n, MOD - 2); } // A Function to calculate the prefix hash static void computePrefixHash(String str, int n, int[] prefix, int[] power) { prefix[0] = 0; prefix[1] = str[0]; for (int i = 2; i <= n; i++) { prefix[i] = (prefix[i - 1] % MOD + (str[i - 1] % MOD * power[i - 1] % MOD) % MOD) % MOD; } return; } // A Function to calculate the suffix hash // Suffix hash is nothing but the prefix hash of // the reversed string static void computeSuffixHash(String str, int n, int[] suffix, int[] power) { 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 * power[j - 1] % MOD) % MOD) % MOD; } return; } // A Function to answer the Queries static void queryResults(String str, Query[] q, int m, int n, int[] prefix, int[] suffix, int[] power) { for (int i = 0; i <= m - 1; i++) { int L = q[i].L; int R = q[i].R; // Hash Value of Substring [L, R] long hash_LR = ((prefix[R + 1] - prefix[L] + MOD) % MOD * findMMI(power[L]) % MOD) % MOD; // Reverse Hash Value of Substring [L, R] long reverse_hash_LR = ((suffix[n - L] - suffix[n - R - 1] + MOD) % MOD * findMMI(power[n - R - 1]) % MOD) % MOD; // If both are equal then the substring is a palindrome if (hash_LR == reverse_hash_LR) { if (isPalindrome(str, L, R) == true) { Console.Write("The Substring [{0} {1}] is a " + "palindrome\n", L, R); } else { Console.Write("The Substring [{0} {1}] is not a " + "palindrome\n", L, R); } } else { Console.Write("The Substring [{0} {1}] is not a " + "palindrome\n", L, R); } } return; } // A Dynamic Programming Based Approach to compute the // powers of 101 static void computePowers(int[] power, int n) { // 101^0 = 1 power[0] = 1; for (int i = 1; i <= n; i++) { power[i] = (power[i - 1] % MOD * p % MOD) % MOD; } return; } /* Driver code */ public static void Main(String[] args) { String str = "abaaabaaaba"; int n = str.Length; // A Table to store the powers of 101 int[] power = new int[n + 1]; computePowers(power, n); // Arrays to hold prefix and suffix hash values int[] prefix = new int[n + 1]; int[] suffix = new int[n + 1]; // Compute Prefix Hash and Suffix Hash Arrays computePrefixHash(str, n, prefix, power); computeSuffixHash(str, n, suffix, power); Query[] q = { new Query(0, 10), new Query(5, 8), new Query(2, 5), new Query(5, 9) }; int m = q.Length; queryResults(str, q, m, n, prefix, suffix, power); }}// This code is contributed by Rajput-Ji |
Javascript
<script> // A JavaScript program to answer queries to check whether // the substrings are palindrome or not efficiently // Constant variables const p = 101; const MOD = 1000000007; // Structure to represent a query. A query consists // of (L, R) and we have to answer whether the substring // from index-L to R is a palindrome or not function Query(L, R) { this.L = L; this.R = R; } // A function to check if a string str is palindrome // in the range L to R function isPalindrome(str, L, R) { // Keep comparing characters while they are same while (R > L) { if (str.charAt(L++) != str.charAt(R--)) { return false; } } return true; } // A Function to find pow (base, exponent) % MOD // in log (exponent) time function modPow(base, exponent) { if (exponent == 0) { return 1; } if (exponent == 1) { return base; } let temp = modPow(base, exponent / 2); if (exponent % 2 == 0) { return (temp % MOD * temp % MOD) % MOD; } else { return (((temp % MOD * temp % MOD) % MOD) * base % MOD) % MOD; } } // A Function to calculate // Modulo Multiplicative Inverse of 'n' function findMMI(n) { return modPow(n, MOD - 2); } // A Function to calculate the prefix hash function computePrefixHash(str, n, prefix, power) { prefix[0] = 0; prefix[1] = str.charAt(0); for (let i = 2; i <= n; i++) { prefix[i] = (prefix[i - 1] % MOD + (str.charAt(i - 1) % MOD * power[i - 1] % MOD) % MOD) % MOD; } } // A Function to calculate the suffix hash // Suffix hash is nothing but the prefix hash of // the reversed string function computeSuffixHash(str, n, suffix, power) { suffix[0] = 0; suffix[1] = str.charAt(n - 1); for (let i = n - 2, j = 2; i >= 0 && j <= n; i--, j++) { suffix[j] = (suffix[j - 1] % MOD + (str.charAt(i) % MOD * power[j - 1] % MOD) % MOD) % MOD; } } // A Function to answer the Queries function queryResults(str, q, m, n, prefix, suffix, power) { for (let i = 0; i <= m - 1; i++) { let L = q[i].L; let R = q[i].R; // Hash Value of Substring [L, R] let hash_LR = ((prefix[R + 1] - prefix[L] + MOD) % MOD * findMMI(power[L]) % MOD) % MOD; // Reverse Hash Value of Substring [L, R] let reverse_hash_LR = ((suffix[n - L] - suffix[n - R - 1] + MOD) % MOD * findMMI(power[n - R - 1]) % MOD) % MOD; // If both are equal then the substring is a palindrome if (hash_LR == reverse_hash_LR) { if (isPalindrome(str, L, R) == true) { console.log("The Substring [" + L + " " + R + "] is a " + "palindrome"); } else { console.log("The Substring [" + L + " " + R + "] is not a " + "palindrome"); } } else { console.log("The Substring [" + L + " " + R + "] is not a " + "palindrome"); } } } // A Dynamic Programming Based Approach to compute the // powers of 101 function computePowers(power, n) { // 101^0 = 1 power[0] = 1; for (let i = 1; i <= n; i++) { power[i] = (power[i - 1] % MOD * p % MOD) % MOD; } } // Driver code function main() { let str = "abaaabaaaba"; let n = str.length; // A Table to store the powers of 101 let power = new Array(n + 1); computePowers(power, n); // Arrays to hold prefix and suffix hash values let prefix = new Array(n + 1); let suffix = new Array(n + 1); // Compute Prefix Hash and Suffix Hash Arrays computePrefixHash(str, n, prefix, power); computeSuffixHash(str, n, suffix, power); let q = [new Query(0, 10), new Query(5, 8), new Query(2, 5), new Query(5, 9)]; let m = q.length; queryResults(str, q, m, n, prefix, suffix, power); } // Call main function main(); // This code is contributed by Susobhan Akhuli</script> |
Output
The Substring [0 10] is a palindrome The Substring [5 8] is not a palindrome The Substring [2 5] is not a palindrome The Substring [5 9] is a palindrome
Time complexity: O(n*m) where m is the number of queries and n is the length of the string.
Auxiliary Space: O(n)
This article is contributed by Rachit Belwariar. If you like neveropen and would like to contribute, you can also write an article and mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
