Given two strings S and T of length N and M respectively, the task is to count the number of substrings of S that contains the string T in it as a substring.
Examples:
Input: S = “dabc”, T = “ab”
Output: 4
Explanation:
Substrings of S containing T as a substring are:
- S[0, 2] = “dab”
- S[1, 2] = “ab”
- S[1, 3] = “abc”
- S[0, 3] = “dabc”
Input: S = “hshshshs” T = “hs”
Output: 25
Naive Approach: For the simplest approach to solve the problem, refer to the previous post of this article.
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Efficient Approach: To optimize the above approach, the idea is to find out all the occurrences of T in S. Whenever T is found in S, add all the substrings which contain this occurrence of T excluding the substrings which were already calculated in the previous occurrences. Follow the steps below to solve the problem:
- Initialize a variable, say answer, to store the count of substrings.
- Initialize a variable, say last, to store the starting index of the last occurrence of T in S.
- Iterate over the range [0, N – M] using a variable, say i.
- Check if the substring S[i, i + M] is equal to T or not. If found to be true, then add (i + 1 – last) * (N – (i + M – 1)) to answer and update last to (i + 1).
- Otherwise, continue for the next iteration.
- After completing the above steps, print the value of the answer as the result.
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 the substrings of// string containing another given// string as a substringvoid findOccurrences(string S, string T){ // Store length of string S int n1 = S.size(); // Store length of string T int n2 = T.size(); // Store the required count of // substrings int ans = 0; // Store the starting index of // last occurrence of T in S int last = 0; // Iterate in range [0, n1-n2] for (int i = 0; i <= n1 - n2; i++) { // Check if substring from i // to i + n2 is equal to T bool chk = true; // Check if substring from i // to i + n2 is equal to T for (int j = 0; j < n2; j++) { // Mark chk as false and // break the loop if (T[j] != S[i + j]) { chk = false; break; } } // If chk is true if (chk) { // Add (i + 1 - last) * // (n1 - (i + n2 - 1)) // to answer ans += (i + 1 - last) * (n1 - (i + n2 - 1)); // Update the last to i + 1 last = i + 1; } } // Print the answer cout << ans;}// Driver codeint main(){ string S = "dabc", T = "ab"; // Function Call findOccurrences(S, T);} |
Java
// Java program for the above approachclass GFG{ // Function to count the substrings of// string containing another given// string as a substringstatic void findOccurrences(String S, String T){ // Store length of string S int n1 = S.length(); // Store length of string T int n2 = T.length(); // Store the required count of // substrings int ans = 0; // Store the starting index of // last occurrence of T in S int last = 0; // Iterate in range [0, n1-n2] for (int i = 0; i <= n1 - n2; i++) { // Check if substring from i // to i + n2 is equal to T boolean chk = true; // Check if substring from i // to i + n2 is equal to T for (int j = 0; j < n2; j++) { // Mark chk as false and // break the loop if (T.charAt(j) != S.charAt(i + j)) { chk = false; break; } } // If chk is true if (chk) { // Add (i + 1 - last) * // (n1 - (i + n2 - 1)) // to answer ans += (i + 1 - last) * (n1 - (i + n2 - 1)); // Update the last to i + 1 last = i + 1; } } // Print the answer System.out.println(ans);} // Driver code public static void main (String[] args) { String S = "dabc", T = "ab"; // Function Call findOccurrences(S, T); }}// This code is contributed by AnkThon |
Python3
# Python3 program for the above approach# Function to count the substrings of# containing another given# as a subdef findOccurrences(S, T): # Store length of S n1 = len(S) # Store length of T n2 = len(T) # Store the required count of # substrings ans = 0 # Store the starting index of # last occurrence of T in S last = 0 # Iterate in range [0, n1-n2] for i in range(n1 - n2 + 1): # Check if subfrom i # to i + n2 is equal to T chk = True # Check if subfrom i # to i + n2 is equal to T for j in range(n2): # Mark chk as false and # break the loop if (T[j] != S[i + j]): chk = False break # If chk is true if (chk): # Add (i + 1 - last) * # (n1 - (i + n2 - 1)) # to answer ans += (i + 1 - last) * (n1 - (i + n2 - 1)) # Update the last to i + 1 last = i + 1 # Print the answer print(ans)# Driver codeif __name__ == '__main__': S,T = "dabc","ab" # Function Call findOccurrences(S, T)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{ // Function to count the substrings of// string containing another given// string as a substringstatic void findOccurrences(String S, String T){ // Store length of string S int n1 = S.Length; // Store length of string T int n2 = T.Length; // Store the required count of // substrings int ans = 0; // Store the starting index of // last occurrence of T in S int last = 0; // Iterate in range [0, n1-n2] for (int i = 0; i <= n1 - n2; i++) { // Check if substring from i // to i + n2 is equal to T bool chk = true; // Check if substring from i // to i + n2 is equal to T for (int j = 0; j < n2; j++) { // Mark chk as false and // break the loop if (T[j] != S[i + j]) { chk = false; break; } } // If chk is true if (chk) { // Add (i + 1 - last) * // (n1 - (i + n2 - 1)) // to answer ans += (i + 1 - last) * (n1 - (i + n2 - 1)); // Update the last to i + 1 last = i + 1; } } // Print the answer Console.WriteLine(ans);} // Driver code public static void Main(String[] args) { String S = "dabc", T = "ab"; // Function Call findOccurrences(S, T); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript program for above approach// Function to count the substrings of// string containing another given// string as a substringfunction findOccurrences(S, T){ // Store length of string S let n1 = S.length; // Store length of string T let n2 = T.length; // Store the required count of // substrings let ans = 0; // Store the starting index of // last occurrence of T in S let last = 0; // Iterate in range [0, n1-n2] for (let i = 0; i <= n1 - n2; i++) { // Check if substring from i // to i + n2 is equal to T let chk = true; // Check if substring from i // to i + n2 is equal to T for (let j = 0; j < n2; j++) { // Mark chk as false and // break the loop if (T[j] != S[i + j]) { chk = false; break; } } // If chk is true if (chk) { // Add (i + 1 - last) * // (n1 - (i + n2 - 1)) // to answer ans += (i + 1 - last) * (n1 - (i + n2 - 1)); // Update the last to i + 1 last = i + 1; } } // Print the answer document.write(ans);}// Driver Code let S = "dabc", T = "ab"; // Function Call findOccurrences(S, T); </script> |
Output:
4
Time Complexity: O(N*M) since two nested loops are used where N and M are the lengths of given strings.
Auxiliary Space: O(1) since no extra array is used the space occupied by the algorithm is constant.
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!
