Given three strings S, X, and Y consisting of N, A, and B characters respectively, the task is to find the number of occurrences of the substring X before every occurrence of the substring Y in the given string S.
Examples:
Input S = ”abcdefdefabc”, X = ”def”, Y = ”abc”
Output: 0 2
Explanation:
First occurrence of Y(= “abc”): No of occurrences of X(= “def”) = 0.
Second occurrence of Y: No of occurrences of X = 0.Input: S = ”accccbbbbbbaaa”, X = ”a”, Y = ”b”
Output: 0 6 6 6
Approach: Follow the steps below to solve the problem:
- Initialize a variable, say count, that stores the total number occurrences of X.
- Traverse the given string S and perform the following steps:
- If the substring over the range [i, B] is equal to Y, then increment count by 1.
- If the substring over the range [i, A] is equal to X, then print the value of count as the resultant count of the string Y before the current occurrence of the string X.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count occurrences of// the string Y in the string S for// every occurrence of X in Svoid countOccurrences(string S, string X, string Y){ // Stores the count of // occurrences of X int count = 0; // Stores the lengths of the // three strings int N = S.length(), A = X.length(); int B = Y.length(); // Traverse the string S for (int i = 0; i < N; i++) { // If the current substring // is Y, then increment the // value of count by 1 if (S.substr(i, B) == Y) count++; // If the current substring // is X, then print the count if (S.substr(i, A) == X) cout << count << " "; }}// Driver Codeint main(){ string S = "abcdefdefabc"; string X = "abc"; string Y = "def"; countOccurrences(S, X, Y); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;public class GFG { // Function to count occurrences of // the string Y in the string S for // every occurrence of X in S static void countOccurrences(String S, String X, String Y) { // Stores the count of // occurrences of X int count = 0; // Stores the lengths of the // three strings int N = S.length(), A = X.length(); int B = Y.length(); // Traverse the string S for (int i = 0; i < N; i++) { // If the current substring // is Y, then increment the // value of count by 1 if (S.substring(i, Math.min(N, i + B)) .equals(Y)) count++; // If the current substring // is X, then print the count if (S.substring(i, Math.min(N, i + A)) .equals(X)) System.out.print(count + " "); } } // Driver Code public static void main(String[] args) { String S = "abcdefdefabc"; String X = "abc"; String Y = "def"; countOccurrences(S, X, Y); }}// This code is contributed by Kingash. |
Python3
# Python program for the above approach# Function to count occurrences of# the string Y in the string S for# every occurrence of X in Sdef countOccurrences(S, X, Y): # Stores the count of # occurrences of X count = 0 # Stores the lengths of the # three strings N = len(S) A = len(X) B = len(Y) # Traverse the string S for i in range( 0, N): # If the current substring # is Y, then increment the # value of count by 1 if (S[i: i+B] == Y): count+=1 # If the current substring # is X, then print the count if (S[i:i+A] == X): print(count, end = " ") # Driver CodeS = "abcdefdefabc"X = "abc"Y = "def"countOccurrences(S, X, Y)# This code is contributed by rohitsingh07052. |
C#
// C# program for the above approachusing System;public class GFG { // Function to count occurrences of // the string Y in the string S for // every occurrence of X in S static void countOccurrences(string S, string X, string Y) { // Stores the count of // occurrences of X int count = 0; // Stores the lengths of the // three strings int N = S.Length, A = X.Length; int B = Y.Length; int P = Math.Min(A, Math.Min(N, B)); // Traverse the string S for (int i = 0; i < N - P + 1; i++) { // If the current substring // is Y, then increment the // value of count by 1 if (S.Substring(i, Math.Min(N, B)).Equals(Y)) count++; // If the current substring // is X, then print the count if (S.Substring(i, Math.Min(N, A)).Equals(X)) Console.Write(count + " "); } } // Driver Code public static void Main(string[] args) { string S = "abcdefdefabc"; string X = "abc"; string Y = "def"; countOccurrences(S, X, Y); }}// This code is contributed by ukasp. |
Javascript
<script>// Js program for the above approach// Function to count occurrences of// the string Y in the string S for// every occurrence of X in Sfunction countOccurrences( S, X, Y){ // Stores the count of // occurrences of X let count = 0; // Stores the lengths of the // three strings let N = S.length, A = X.length; let B = Y.length; // Traverse the string S for (let i = 0; i < N; i++) { // If the current substring // is Y, then increment the // value of count by 1 if (S.substr(i, B) == Y) count++; // If the current substring // is X, then print the count if (S.substr(i, A) == X) document.write(count," "); }}// Driver Codelet S = "abcdefdefabc", X = "abc", Y = "def";countOccurrences(S, X, Y);</script> |
Output:
0 2
Time Complexity: O(N*(A + B)), as we are using a loop to traverse N times and we are using inbuilt substring function which will cost us the O(A+B) time.
Auxiliary Space: O(1), as we are not using any extra space.
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!
