Given two strings A, B and some queries consisting of an integer i, the task is to check whether the sub-string of A starting from index i and ending at index i + length(B) – 1 equals B or not. If equal then print Yes else print No. Note that i + length(B) will always be smaller than length(A).
Examples:
Input: A = “abababa”, B = “aba”, q[] = {0, 1, 2, 3}
Output:
Yes
No
Yes
No
a[0-2] = “aba” = b (both are equal)
a[1-3] = “bab” != b
a[2-4] = “aba” = b
a[3-5] = “bab” !=bInput: A = “GeeksForGeeks”, B = “Geeks”, q[] = {0, 5, 8}
Output:
Yes
No
Yes
A simple approach will be to compare the strings character by character for every query which will take O(length(B)) time to answer each query.
Efficient approach: We will optimize the query processing using rolling hash algorithm.
First, we will find hash value of string B. Then, using rolling hash technique, we will do the pre-processing of string A.
Let’s suppose we created an array hash_A. Then ith element of this array will store.
((a[0] – 97) + (a[1] – 97) * d + (a[2] – 97) * d2 + ….. + (a[i] – 97) * di) % mod
where d is the multiplier in rolling-hash.
We will use this to find hash of the sub-string of A.
Hash of sub-string of A starting from i can be found as (hash_a[i + len_b – 1] – hash_a[i – 1]) / di or more specifically
((hash_a[i + len_b – 1] – hash_a[i – 1] + 2 * mod) * mi(di)) % mod
Thus, using this we can answer each query in O(1).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>#define mod 3803#define d 26using namespace std;int hash_b;int* hash_a;int* mul;// Function to return the modular inverse// using Fermat's little theoremint mi(int x){ int p = mod - 2; int s = 1; while (p != 1) { if (p % 2 == 1) s = (s * x) % mod; x = (x * x) % mod; p /= 2; } return (s * x) % mod;}// Function to generate hashvoid genHash(string& a, string& b){ // To store prefix-sum // of rolling hash hash_a = new int[a.size()]; // Multiplier for different values of i mul = new int[a.size()]; // Generating hash value for string b for (int i = b.size() - 1; i >= 0; i--) hash_b = (hash_b * d + (b[i] - 97)) % mod; // Generating prefix-sum of hash of a mul[0] = 1; hash_a[0] = (a[0] - 97) % mod; for (int i = 1; i < a.size(); i++) { mul[i] = (mul[i - 1] * d) % mod; hash_a[i] = (hash_a[i - 1] + mul[i] * (a[i] - 97)) % mod; }}// Function that returns true if the// required sub-string in a is equal to bbool checkEqual(int i, int len_a, int len_b){ // To store hash of required // sub-string of A int x; // If i = 0 then // requires hash value if (i == 0) x = hash_a[len_b - 1]; // Required hash if i != 0 else { x = (hash_a[i + len_b - 1] - hash_a[i - 1] + 2 * mod) % mod; x = (x * mi(mul[i])) % mod; } // Comparing hash with hash of B if (x == hash_b) return true; return false;}// Driver codeint main(){ string a = "abababababa"; string b = "aba"; // Generating hash genHash(a, b); // Queries int queries[] = { 0, 1, 2, 3 }; int q = sizeof(queries) / sizeof(queries[0]); // Perform queries for (int i = 0; i < q; i++) { if (checkEqual(queries[i], a.size(), b.size())) cout << "Yes\n"; else cout << "No\n"; } return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG { static int mod = 3803; static int d = 26; static int hash_b; static int[] hash_a; static int[] mul; // Function to return the modular inverse // using Fermat's little theorem static int mi(int x) { int p = mod - 2; int s = 1; while (p != 1) { if (p % 2 == 1) { s = (s * x) % mod; } x = (x * x) % mod; p /= 2; } return (s * x) % mod; } // Function to generate hash static void genHash(char[] a, char[] b) { // To store prefix-sum // of rolling hash hash_a = new int[a.length]; // Multiplier for different values of i mul = new int[a.length]; // Generating hash value for string b for (int i = b.length - 1; i >= 0; i--) { hash_b = (hash_b * d + (b[i] - 97)) % mod; } // Generating prefix-sum of hash of a mul[0] = 1; hash_a[0] = (a[0] - 97) % mod; for (int i = 1; i < a.length; i++) { mul[i] = (mul[i - 1] * d) % mod; hash_a[i] = (hash_a[i - 1] + mul[i] * (a[i] - 97)) % mod; } } // Function that returns true if the // required sub-string in a is equal to b static boolean checkEqual(int i, int len_a, int len_b) { // To store hash of required // sub-string of A int x; // If i = 0 then // requires hash value if (i == 0) { x = hash_a[len_b - 1]; } // Required hash if i != 0 else { x = (hash_a[i + len_b - 1] - hash_a[i - 1] + 2 * mod) % mod; x = (x * mi(mul[i])) % mod; } // Comparing hash with hash of B if (x == hash_b) { return true; } return false; } // Driver code public static void main(String[] args) { String a = "abababababa"; String b = "aba"; // Generating hash genHash(a.toCharArray(), b.toCharArray()); // Queries int queries[] = { 0, 1, 2, 3 }; int q = queries.length; // Perform queries for (int i = 0; i < q; i++) { if (checkEqual(queries[i], a.length(), b.length())) { System.out.println("Yes"); } else { System.out.println("No"); } } }}/* This code is contributed by PrinciRaj1992 */ |
Python3
# Python3 implementation of the approachmod = 3803d = 26hash_b = 0hash_a = []mul = []# Function to return the modular inverse# using Fermat's little theoremdef mi(x): global mod p = mod - 2 s = 1 while p != 1: if p % 2 == 1: s = (s * x) % mod x = (x * x) % mod p //= 2 return (s * x) % mod# Function to generate hashdef genHash(a, b): global hash_b, hash_a, mul, d, mod # To store prefix-sum # of rolling hash hash_a = [0] * len(a) # Multiplier for different values of i mul = [0] * len(a) # Generating hash value for string b for i in range(len(b) - 1, -1, -1): hash_b = (hash_b * d + (ord(b[i]) - 97)) % mod # Generating prefix-sum of hash of a mul[0] = 1 hash_a[0] = (ord(a[0]) - 97) % mod for i in range(1, len(a)): mul[i] = (mul[i - 1] * d) % mod hash_a[i] = (hash_a[i - 1] + mul[i] * (ord(a[i]) - 97)) % mod# Function that returns true if the# required sub-string in a is equal to bdef checkEqual(i, len_a, len_b): global hash_b, hash_a, mul, d, mod # To store hash of required # sub-string of A x = -1 # If i = 0 then # requires hash value if i == 0: x = hash_a[len_b - 1] # Required hash if i != 0 else: x = (hash_a[i + len_b - 1] - hash_a[i - 1] + 2 * mod) % mod x = (x * mi(mul[i])) % mod # Comparing hash with hash of B if x == hash_b: return True return False# Driver Codeif __name__ == "__main__": a = "abababababa" b = "aba" # Generating hash genHash(a, b) # Queries queries = [0, 1, 2, 3] q = len(queries) # Perform queries for i in range(q): if checkEqual(queries[i], len(a), len(b)): print("Yes") else: print("No")# This code is contributed by# sanjeev2552 |
C#
// C# implementation of the approachusing System;class GFG { static int mod = 3803; static int d = 26; static int hash_b; static int[] hash_a; static int[] mul; // Function to return the modular inverse // using Fermat's little theorem static int mi(int x) { int p = mod - 2; int s = 1; while (p != 1) { if (p % 2 == 1) { s = (s * x) % mod; } x = (x * x) % mod; p /= 2; } return (s * x) % mod; } // Function to generate hash static void genHash(char[] a, char[] b) { // To store prefix-sum // of rolling hash hash_a = new int[a.Length]; // Multiplier for different values of i mul = new int[a.Length]; // Generating hash value for string b for (int i = b.Length - 1; i >= 0; i--) { hash_b = (hash_b * d + (b[i] - 97)) % mod; } // Generating prefix-sum of hash of a mul[0] = 1; hash_a[0] = (a[0] - 97) % mod; for (int i = 1; i < a.Length; i++) { mul[i] = (mul[i - 1] * d) % mod; hash_a[i] = (hash_a[i - 1] + mul[i] * (a[i] - 97)) % mod; } } // Function that returns true if the // required sub-string in a is equal to b static Boolean checkEqual(int i, int len_a, int len_b) { // To store hash of required // sub-string of A int x; // If i = 0 then // requires hash value if (i == 0) { x = hash_a[len_b - 1]; } // Required hash if i != 0 else { x = (hash_a[i + len_b - 1] - hash_a[i - 1] + 2 * mod) % mod; x = (x * mi(mul[i])) % mod; } // Comparing hash with hash of B if (x == hash_b) { return true; } return false; } // Driver code public static void Main(String[] args) { String a = "abababababa"; String b = "aba"; // Generating hash genHash(a.ToCharArray(), b.ToCharArray()); // Queries int[] queries = { 0, 1, 2, 3 }; int q = queries.Length; // Perform queries for (int i = 0; i < q; i++) { if (checkEqual(queries[i], a.Length, b.Length)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } } }}/* This code contributed by PrinciRaj1992 */ |
Javascript
<script>// Javascript implementation of the approachvar mod = 3803;var d = 26;var hash_b = 0;var hash_a = [];var mul = [];// Function to return the modular inverse// using Fermat's little theoremfunction mi(x){ var p = mod - 2; var s = 1; while (p != 1) { if (p % 2 == 1) s = (s * x) % mod; x = (x * x) % mod; p = parseInt(p/2); } return (s * x) % mod;}// Function to generate hashfunction genHash(a, b){ // To store prefix-sum // of rolling hash hash_a = Array(a.length).fill(0); // Multiplier for different values of i mul = Array(a.length).fill(0); // Generating hash value for string b for (var i = b.length - 1; i >= 0; i--) hash_b = (hash_b * d + (b[i].charCodeAt(0) - 97)) % mod; // Generating prefix-sum of hash of a mul[0] = 1; hash_a[0] = (a[0].charCodeAt(0) - 97) % mod; for (var i = 1; i < a.length; i++) { mul[i] = (mul[i - 1] * d) % mod; hash_a[i] = (hash_a[i - 1] + mul[i] * (a[i].charCodeAt(0) - 97)) % mod; }}// Function that returns true if the// required sub-string in a is equal to bfunction checkEqual(i, len_a, len_b){ // To store hash of required // sub-string of A var x; // If i = 0 then // requires hash value if (i == 0) x = hash_a[len_b - 1]; // Required hash if i != 0 else { x = (hash_a[i + len_b - 1] - hash_a[i - 1] + 2 * mod) % mod; x = (x * mi(mul[i])) % mod; } // Comparing hash with hash of B if (x == hash_b) return true; return false;}// Driver codevar a = "abababababa";var b = "aba";// Generating hashgenHash(a.split(''), b.split(''));// Queriesvar queries = [0, 1, 2, 3];var q = queries.length// Perform queriesfor (var i = 0; i < q; i++) { if (checkEqual(queries[i], a.length, b.length)) document.write("Yes<br>"); else document.write("No<br>");}// This code is contributed by rrrtnx.</script> |
Output
Yes No Yes No
Time Complexity: O(N*Q)
Auxiliary Space: O(M*N)
Note: For simplicity, we have used only one hash function. Use double/triple hash to eliminate any chance of collision and more accurate result.
The above question can be solved by using DP also, below is the java code.
C++
#include <bits/stdc++.h>using namespace std;void substringCheck(string stra, string strb, vector<int> query){ // Dp Array int matrix[strb.size()][stra.size()]; // initialize matrix with 1 for (int c = 0; c < stra.size(); c++) { if (strb[0] == stra) { matrix[0] = 1; } } // for r from 1 to string length for (int r = 1; r < strb.size(); r++) { char ch = strb[r]; // for c from 1 b string length for (int c = 1; c < stra.size(); c++) { if (ch == stra && matrix[r - 1] == 1) { matrix[r] = 1; } } } // For every query for (auto q : query) { int matLoc = (q + (strb.size() - 1)); if (matLoc >= stra.size()) { cout << "false" << endl; } else { // print true if (matrix[strb.size() - 1][(matLoc)] == 1) { cout << "true" << endl; } else { // print false cout << "false" << endl; } } }}// Driver Codeint main(){ string stra = "GeeksForGeeks"; string strb = "Geeks"; vector<int> query = { 0, 5, 8 }; substringCheck(stra, strb, query);}// This code is contributed by Samim Hossain Mondal. |
Java
import java.io.*;import java.util.*;import java.lang.*;import java.io.*;public class GFG{ private static void substringCheck(String stra, String strb, int[] query) { // Dp Array int[][] matrix = new int[strb.length()][stra.length()]; // String to character array char[] charCrr = stra.toCharArray(); char[] charRrr = strb.toCharArray(); // initialize matrix with 1 for (int c = 0; c < stra.length(); c++) { if (charRrr[0] == charCrr) { matrix[0] = 1; } } // for r from 1 to string length for (int r = 1; r < charRrr.length; r++) { char ch = charRrr[r]; // for c from 1 b string length for (int c = 1; c < charCrr.length; c++) { if (ch == charCrr && matrix[r - 1] == 1) { matrix[r] = 1; } } } // For every query for (int q : query) { int matLoc = (q + (strb.length() - 1)); if (matLoc >= stra.length()) { System.out.println(false); } else { // print true if (matrix[strb.length() - 1][(matLoc)] == 1) { System.out.println(true); } else { // print false System.out.println(false); } } } } // Driver Code public static void main(String[] args) { String stra = "GeeksForGeeks"; String strb = "Geeks"; int[] query = { 0,5,8 }; substringCheck(stra, strb, query); }} // class// Code contributed by Swapnil Gupta |
Python3
def substringCheck(stra, strb, query): # Dp Array # matrix[strb.size()][stra.size()]; n = len(stra) m = len(strb) matrix = [[-1] * n for _ in range(m)] # initialize matrix with 1 for c in range(n): if strb[0] == stra: matrix[0] = 1 # for r from 1 to string length for r in range(1, m): ch = strb[r] # for c from 1 b string length for c in range(1, n): if ch == stra and matrix[r - 1] == 1: matrix[r] = 1 # For every query for q in query: matLoc = q + (m - 1) if matLoc >= n: print("false") else: # print true if matrix[m - 1][(matLoc)] == 1: print("true") else: # print false print("false")# Driver Codeif __name__ == "__main__": stra = "GeeksForGeeks" strb = "Geeks" query = [0, 5, 8] substringCheck(stra, strb, query) |
C#
using System;public class GFG { private static void substringCheck(string stra, string strb, int[] query) { // Dp Array int[, ] matrix = new int[strb.Length, stra.Length]; // String to character array char[] charCrr = stra.ToCharArray(); char[] charRrr = strb.ToCharArray(); // initialize matrix with 1 for (int c = 0; c < stra.Length; c++) { if (charRrr[0] == charCrr) { matrix[0, c] = 1; } } // for r from 1 to string length for (int r = 1; r < charRrr.Length; r++) { char ch = charRrr[r]; // for c from 1 b string length for (int c = 1; c < charCrr.Length; c++) { if (ch == charCrr && matrix[r - 1, c - 1] == 1) { matrix[r, c] = 1; } } } // For every query foreach(int q in query) { int matLoc = (q + (strb.Length - 1)); if (matLoc >= stra.Length) { Console.WriteLine(false); } else { // print true if (matrix[strb.Length - 1, matLoc] == 1) { Console.WriteLine(true); } else { // print false Console.WriteLine(false); } } } } // Driver Code public static void Main(string[] args) { string stra = "GeeksForGeeks"; string strb = "Geeks"; int[] query = { 0, 5, 8 }; substringCheck(stra, strb, query); }}// This code is contributed by ukasp. |
Javascript
<script>function substringCheck(stra, strb, query){ // Dp Array var matrix = Array.from(Array(strb.length), ()=>Array(stra.length)); // String to character array var charCrr = stra.split(''); var charRrr = strb.split(''); // initialize matrix with 1 for (var c = 0; c < stra.length; c++) { if (charRrr[0] == charCrr) { matrix[0] = 1; } } // for r from 1 to string length for (var r = 1; r < charRrr.length; r++) { var ch = charRrr[r]; // for c from 1 b string length for (var c = 1; c < charCrr.length; c++) { if (ch == charCrr && matrix[r - 1] == 1) { matrix[r] = 1; } } } // For every query for (var q of query) { var matLoc = (q + (strb.length - 1)); if (matLoc >= stra.length) { document.write(false + "<br>"); } else { // print true if (matrix[strb.length - 1][(matLoc)] == 1) { document.write(true+ "<br>"); } else { // print false document.write(false+ "<br>"); } } }}// Driver Codevar stra = "GeeksForGeeks";var strb = "Geeks";var query = [0,5,8];substringCheck(stra, strb, query);// This code is contributed by rutvik_56.</script> |
Output
true false true
Time Complexity: O(M*N)
Auxiliary Space: O(M*N)
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!
