What is Count occurrences of a substring recursively?

In this article, we will learn Count occurrences of a substring recursively,This free C++ tutorial for complete beginners will help you learn C++ from scratch.

Count occurrences of a substring recursively️‍🔥

Q: How to use Count occurrences of a substring recursively in C++?

Given two strings str1 and str2, the task is to count the number of times str2 occurs in str1 using recursion

Given two strings str1 and str2, the task is to count the number of times str2 occurs in str1 using recursion.

Examples:

Input: str1 = “w3wiki”, str2 = “geek”
Output: 2
Explanation: The occurrences of str2 in str1 are starting at index {0, 8}

Input: str1 = “aaaaa”, str2 = “aaa”
Output: 3
Explanation: The occurrences of str2 in str1 are starting at index {0,1,2

Approach: We have already discussed other approaches in our previous article but here we are going to solve this problem using recursion.

Algorithm:

If size of string str2 is greater then string str1 or size of string str1 is 0 then, return 0.
Otherwise, Check if string str2 is present in str1 as substring or not.
- if present then, increment the count of occurrence and recursively call for other substring.
- else, recursively call for other substring.
- return count from every recursively call as answer.

Below is the implementation of the above approach:

C++

// Recursive C++ program to count the number of
// times string str2 occurs in string str1 
 
#include <iostream>
#include <string>
using namespace std;
 
// Function to count the number of
// times string str2 occurs in string str1
int countSubstring(string str1, string str2)
{
    int n1 = str1.length();
    int n2 = str2.length();
 
    // Base Case
    if (n1 == 0 || n1 < n2)
        return 0;
 
    // Recursive Case
    // Checking if the first substring matches
    if (str1.substr(0, n2).compare(str2) == 0)
        return countSubstring(str1.substr(1), str2) + 1;
 
    // Otherwise, return the count from
    // the remaining index
    return countSubstring(str1.substr(1), str2);
}
 
 
// Driver function
int main()
{
    string str1 = "w3wiki", str2 = "Beginner";
    cout << countSubstring(str1, str2) << endl;
   
      str1 = "aaaaa", str2 = "aaa";
    cout << countSubstring(str1, str2) << endl;
 
    return 0;
}

Java

// Recursive Java program for
// counting number of substrings
class GFG
{
 
// Recursive function to 
// count the number of 
// occurrences of "hi" in str.
static int countSubstring(String str1, 
                         String str2)
{
    int n1 = str1.length();
    int n2 = str2.length();
 
    // Base Case
    if (n1 == 0 || n1 < n2)
        return 0;
 
    // Recursive Case
    // Checking if the first
    // substring matches
    if (str1.substring(0, n2).equals(str2))
        return countSubstring(str1.substring(1), 
                                            str2) + 1;
 
    // Otherwise, return the count 
    // from the remaining index
    return countSubstring(str1.substring(1), 
                                        str2);
}
 
// Driver Code
public static void main(String args[])
{
    String str1 = "w3wiki", 
           str2 = "Beginner";
    System.out.println(countSubstring(str1, 
                                     str2));
 
    str1 = "aaaaa";
    str2 = "aaa";
    System.out.println(countSubstring(str1, 
                                     str2));
 
}
}
 
// This code is contributed 
// by Arnab Kundu

Python3

# Recursive Python3 program for
# counting number of substrings
 
# Recursive function to 
# count the number of 
# occurrences of "hi" in str.
def countSubstring(str1, str2):
     
    n1 = len(str1);
    n2 = len(str2);
     
    # Base Case
    if (n1 == 0 or n1 < n2):
        return 0;
 
    # Recursive Case
    # Checking if the first
    # substring matches
    if (str1[0 : n2] == str2):
        return countSubstring(str1[1:], 
                             str2) + 1;
 
    # Otherwise, return the count 
    # from the remaining index
    return countSubstring(str1[1:], 
                         str2);
 
# Driver Code
if __name__ == '__main__':
     
    str1 = "w3wiki"; 
    str2 = "Beginner";
    print(countSubstring(str1, str2));
 
    str1 = "aaaaa";
    str2 = "aaa";
    print(countSubstring(str1, str2));
 
# This code is contributed by Princi Singh

C#

// Recursive C# program for
// counting number of substrings
using System;
class GFG
{
 
// Recursive function to 
// count the number of 
// occurrences of "hi" in str.
static int countSubstring(String str1, 
                         String str2)
{
    int n1 = str1.Length;
    int n2 = str2.Length;
 
    // Base Case
    if (n1 == 0 || n1 < n2)
        return 0;
 
    // Recursive Case
    // Checking if the first
    // substring matches
    if (str1.Substring(0, n2).Equals(str2))
        return countSubstring(str1.Substring(1), 
                                            str2) + 1;
 
    // Otherwise, return the 
    // count from the remaining 
    // index
    return countSubstring(str1.Substring(1), 
                                        str2);
}
 
// Driver Code
public static void Main()
{
    string str1 = "w3wiki", 
           str2 = "Beginner";
    Console.Write(countSubstring(str1, 
                                str2));
    Console.Write("\n");
     
    str1 = "aaaaa";
    str2 = "aaa";
    Console.Write(countSubstring(str1, 
                                str2));
 
}
}
 
// This code is contributed 
// by Smita

Javascript

<script>
 
// Recursive js program for counting number of substrings
 
// Recursive function to count
// the number of occurrences of "hi" in str.
function countSubstring( str1, str2){
    let n1 = str1.length;
    let n2 = str2.length;
 
    // Base Case
    if (n1 == 0 || n1 < n2)
        return 0;
 
    // Recursive Case
    // Checking if the first substring matches
    if (str1.substr(0, n2) == (str2))
        return countSubstring(str1.substr(1), str2) + 1;
 
    // Otherwise, return the count from
    // the remaining index
    return countSubstring(str1.substr(1), str2);
}
 
// Driver function
let str1 = "w3wiki", str2 = "Beginner";
document.write( countSubstring(str1, str2),'<br>');
str1 = "aaaaa", str2 = "aaa";
document.write( countSubstring(str1, str2),'<br>');
 
 
</script>

Output

2
3

Complexity Analysis:

Time Complexity: O(N²) , (i.e. N is maximum length between str1 and str2)
Auxiliary Space: O(1)