Given a string S and a matrix Q of queries, each specifying the starting and ending indices L( = Q[i][0]) and R( = Q[i][0]) respectively of a substring of S, the task is to find the frequency of string K in substring [L, R].
Note: The ranges follow the 1-based indexing.
Examples:
Input: S = “GFGFFGFG”, K = “GFG”, Q = {{1, 8}, {3, 5}, {5, 8}}
Output:
2
0
1
Explanation: For query 1, there are 2 (“GFG”) substrings from index 1 to index 8. One is from index 1 to 3 and the other is from index 6 to 8.
For query 2, there are 0 (“GFG”) substrings from index 3 to 5.
For query 3, there are 1 (“GFG”) substrings from index 5 to index 8. The one and only substring are from index 6 to 8.Input: S = “ABCABCABABC”, K = “ABC”, Q = {{1, 6}, {5, 11}}
Output:
2
1
Naive Approach:
Run a loop from L to R for all the queries. Count occurrence of the string K and return count.
Time Complexity: O(length of Q * |S|).
Efficient Approach:
Pre-compute and store the frequency of K for every index. Now, for computing the frequency of the string in a range [L, R], we just need to calculate the difference between the frequency of K at index (R-1) and (L-1).
Below is the implementation of the above approach:
C++
// C++ Program to find// frequency of a string K// in a substring [L, R] in S#include <bits/stdc++.h>#define max_len 100005using namespace std;// Store the frequency of// string for each indexint cnt[max_len];// Compute and store frequencies// for every indexvoid precompute(string s, string K){ int n = s.size(); for (int i = 0; i < n - 1; i++) { cnt[i + 1] = cnt[i] + (s.substr(i, K.size()) == K); }}// Driver Codeint main(){ string s = "ABCABCABABC"; string K = "ABC"; precompute(s, K); vector<pair<int, int> > Q = { { 1, 6 }, { 5, 11 } }; for (auto it : Q) { cout << cnt[it.second - 1] - cnt[it.first - 1] << endl; } return 0;} |
Java
// Java program to find// frequency of a string K// in a substring [L, R] in Sclass GFG{ static int max_len = 100005;// Store the frequency of// string for each indexstatic int cnt[] = new int[max_len];// Compute and store frequencies// for every indexpublic static void precompute(String s, String K){ int n = s.length(); for(int i = 0; i < n - 2; i++) { cnt[i + 1] = cnt[i]; if (s.substring( i, i + K.length()).equals(K)) { cnt[i + 1] += 1; } } cnt[n - 2 + 1] = cnt[n - 2];}// Driver code public static void main(String[] args){ String s = "ABCABCABABC"; String K = "ABC"; precompute(s, K); int Q[][] = { { 1, 6 }, { 5, 11 } }; for(int it = 0; it < Q.length; it++) { System.out.println(cnt[Q[it][1] - 1] - cnt[Q[it][0] - 1]); }}}// This code is contributed by divyesh072019 |
Python3
# Python3 Program to find# frequency of a string K# in a substring [L, R] in Smax_len = 100005# Store the frequency of# string for each indexcnt = [0] * max_len# Compute and store frequencies# for every indexdef precompute(s, K): n = len(s) for i in range(n - 1): cnt[i + 1] = cnt[i] if s[i : len(K) + i] == K: cnt[i + 1] += 1# Driver Codeif __name__ == "__main__": s = "ABCABCABABC" K = "ABC" precompute(s, K) Q = [[1, 6], [5, 11]] for it in Q: print(cnt[it[1] - 1] - cnt[it[0] - 1])# This code is contributed by Chitranayal |
C#
// C# program to find frequency of// a string K in a substring [L, R] in Susing System.IO;using System;class GFG{ static int max_len = 100005;// Store the frequency of// string for each indexstatic int[] cnt = new int[max_len];// Compute and store frequencies// for every indexstatic void precompute(string s,string K){ int n = s.Length; for(int i = 0; i < n - 2; i++) { cnt[i + 1] = cnt[i]; if (s.Substring(i, K.Length).Equals(K)) { cnt[i + 1] += 1; } } cnt[n - 2 + 1] = cnt[n - 2];}// Driver codestatic void Main(){ string s = "ABCABCABABC"; string K = "ABC"; precompute(s, K); int[,] Q = { { 1, 6 }, { 5, 11 } }; for(int it = 0; it < Q.GetLength(0); it++) { Console.WriteLine(cnt[Q[it, 1] - 1] - cnt[Q[it, 0] - 1]); }}}// This code is contributed by rag2127 |
Javascript
<script>// Javascript program to find// frequency of a string K// in a substring [L, R] in Svar max_len = 100005;// Store the frequency of// string for each indexvar cnt = Array(max_len).fill(0);// Compute and store frequencies// for every indexfunction precompute(s, K){ var n = s.length; for(var i = 0; i < n - 1; i++) { cnt[i + 1] = cnt[i] + (s.substring(i, i + K.length) == K); }}// Driver Codevar s = "ABCABCABABC";var K = "ABC";precompute(s, K);var Q = [ [ 1, 6 ], [ 5, 11 ] ];Q.forEach((it) => { document.write(cnt[it[1] - 1] - cnt[it[0] - 1] + "<br>");});// This code is contributed by itsok</script> |
2 1
Time Complexity: O( | S | + length of Q ), as every query is answered in O(1).
Auxiliary Space: O( |S| )
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
