Posted on by Kalkicode
Code Recursion

# Count occurrences of a substring recursively

In this problem, we are tasked with counting the occurrences of a substring within a given text using recursion. We need to write a program that efficiently counts how many times a given substring appears in the provided text, taking into account all possible starting positions.

## Problem Statement

Given a text string and a substring, our goal is to count how many times the substring occurs in the text. We need to achieve this using a recursive approach.

## Example Scenario

Consider the text "abcaabcccabc" and the substring "abc". In this case, the substring "abc" appears three times in the text, so the output will be 3.

## Idea to Solve the Problem

We can solve this problem recursively by considering each possible starting position in the text and comparing the substring with the text at that position. If a match is found, we increment our count and move on to the next position. This process continues until we have checked all possible positions in the text.

## Pseudocode

``````class Occurrences:
int countSubString(text, substring, i):
if length of text < length of substring or i > length of text - length of substring:
return 0

count = 0
while count < length of substring and (i + count) < length of text
and text[i + count] == substring[count]:
count += 1

if count == length of substring:
return 1 + countSubString(text, substring, i + 1)
return countSubString(text, substring, i + 1)

void countOccurrence(text, substring):
print "Given Text: " + text
print "Substring: " + substring
print "Output   : " + countSubString(text, substring, 0)

main:

## Algorithm Explanation

1. Create a recursive function `countSubString` that takes the `text`, `substring`, and an index `i` as arguments.
2. Inside the function, check if the length of the remaining portion of the `text` is less than the length of the `substring`, or if `i` exceeds the valid index range.
3. If either condition is met, return 0 to stop the recursion.
4. Initialize a variable `count` to 0.
5. Use a loop to compare the characters of the `substring` and `text` starting from index `i`. Increment `count` for each matching character.
6. If `count` reaches the length of the `substring`, it means a complete match is found, so increment the count and make a recursive call to `countSubString` with the next index.
7. If no match is found, continue the recursion by calling `countSubString` with the next index.
8. In the `countOccurrence` function, print the provided text and substring, along with the result of the recursive counting.

## Program Solution

``````/*
Java Program for
Count occurrences of a substring recursively
*/
public class Occurrences
{
// By using recursion count all possible substrings in given text
public int countSubString(String text, String substring, int i)
{
if (text.length() < substring.length()
|| i > text.length() - substring.length())
{
// Stop recursion
return 0;
}

int count = 0;

// Compare substring text
while (count < substring.length() && (i + count) < text.length()
&& text.charAt(i + count) == substring.charAt(count))
{
count += 1;
}
if (count == substring.length())
{
// When substring exist in given text
return 1 + countSubString(text, substring, i + 1);
}
// When substring not exist then try to check substring with next position
return countSubString(text, substring, i + 1);
}
// Handles the request to printing calculate result
public void countOccurrence(String text, String substring)
{
System.out.println(" Given Text : " + text);
System.out.println(" Substring  : " + substring);
System.out.println(" Output     : " + countSubString(text, substring, 0));
}
public static void main(String[] args)
{
// Test Cases
}
}``````

#### input

`````` Given Text : abcaabcccabc
Substring  : abc
Output     : 3
Given Text : coolcool
Substring  : oo
Output     : 2
Given Text : aaaaa
Substring  : aa
Output     : 4
Given Text : aa
Substring  : aa
Output     : 1``````
``````// Include header file
#include <iostream>
#include <string>

using namespace std;
/*
C++ Program for
Count occurrences of a substring recursively
*/
class Occurrences
{
public:
// By using recursion count all possible substrings in given text
int countSubString(string text, string substring, int i)
{
if (text.length() < substring.length()
|| i > text.length() - substring.length())
{
// Stop recursion
return 0;
}
int count = 0;
// Compare substring text
while (count < substring.length() && (i + count) < text.length()
&& text[i + count] == substring[count])
{
count += 1;
}
if (count == substring.length())
{
// When substring exist in given text
return 1 + this->countSubString(text, substring, i + 1);
}
// When substring not exist then try to check substring with next position
return this->countSubString(text, substring, i + 1);
}
// Handles the request to printing calculate result
void countOccurrence(string text, string substring)
{
cout << " Given Text : " << text << endl;
cout << " Substring  : " << substring << endl;
cout << " Output     : " << this->countSubString(text, substring, 0) << endl;
}
};
int main()
{
// Test Cases
return 0;
}``````

#### input

`````` Given Text : abcaabcccabc
Substring  : abc
Output     : 3
Given Text : coolcool
Substring  : oo
Output     : 2
Given Text : aaaaa
Substring  : aa
Output     : 4
Given Text : aa
Substring  : aa
Output     : 1``````
``````// Include namespace system
using System;
/*
Csharp Program for
Count occurrences of a substring recursively
*/
public class Occurrences
{
// By using recursion count all possible substrings in given text
public int countSubString(String text, String substring, int i)
{
if (text.Length < substring.Length || i > text.Length - substring.Length)
{
// Stop recursion
return 0;
}
int count = 0;
// Compare substring text
while (count < substring.Length && (i + count) < text.Length
&& text[i + count] == substring[count])
{
count += 1;
}
if (count == substring.Length)
{
// When substring exist in given text
return 1 + this.countSubString(text, substring, i + 1);
}
// When substring not exist then try to check substring with next position
return this.countSubString(text, substring, i + 1);
}
// Handles the request to printing calculate result
public void countOccurrence(String text, String substring)
{
Console.WriteLine(" Given Text : " + text);
Console.WriteLine(" Substring  : " + substring);
Console.WriteLine(" Output     : " + this.countSubString(text, substring, 0));
}
public static void Main(String[] args)
{
// Test Cases
}
}``````

#### input

`````` Given Text : abcaabcccabc
Substring  : abc
Output     : 3
Given Text : coolcool
Substring  : oo
Output     : 2
Given Text : aaaaa
Substring  : aa
Output     : 4
Given Text : aa
Substring  : aa
Output     : 1``````
``````<?php
/*
Php Program for
Count occurrences of a substring recursively
*/
class Occurrences
{
// By using recursion count all possible substrings in given text
public	function countSubString(\$text, \$substring, \$i)
{
if (strlen(\$text) < strlen(\$substring) || \$i > strlen(\$text) - strlen(\$substring))
{
// Stop recursion
return 0;
}
\$count = 0;
// Compare substring text
while (\$count < strlen(\$substring) && (\$i + \$count) < strlen(\$text) && \$text[\$i + \$count] == \$substring[\$count])
{
\$count += 1;
}
if (\$count == strlen(\$substring))
{
// When substring exist in given text
return 1 + \$this->countSubString(\$text, \$substring, \$i + 1);
}
// When substring not exist then try to check substring with next position
return \$this->countSubString(\$text, \$substring, \$i + 1);
}
// Handles the request to printing calculate result
public	function countOccurrence(\$text, \$substring)
{
echo " Given Text : ".\$text.
"\n";
echo " Substring  : ".\$substring.
"\n";
echo " Output     : ".\$this->countSubString(\$text, \$substring, 0).
"\n";
}
}

function main()
{
// Test Cases
}
main();``````

#### input

`````` Given Text : abcaabcccabc
Substring  : abc
Output     : 3
Given Text : coolcool
Substring  : oo
Output     : 2
Given Text : aaaaa
Substring  : aa
Output     : 4
Given Text : aa
Substring  : aa
Output     : 1``````
``````/*
Node JS Program for
Count occurrences of a substring recursively
*/
class Occurrences
{
// By using recursion count all possible substrings in given text
countSubString(text, substring, i)
{
if (text.length < substring.length || i > text.length - substring.length)
{
// Stop recursion
return 0;
}
var count = 0;
// Compare substring text
while (count < substring.length && (i + count) < text.length && text.charAt(i + count) == substring.charAt(count))
{
count += 1;
}
if (count == substring.length)
{
// When substring exist in given text
return 1 + this.countSubString(text, substring, i + 1);
}
// When substring not exist then try to check substring with next position
return this.countSubString(text, substring, i + 1);
}
// Handles the request to printing calculate result
countOccurrence(text, substring)
{
console.log(" Given Text : " + text);
console.log(" Substring  : " + substring);
console.log(" Output     : " + this.countSubString(text, substring, 0));
}
}

function main()
{
// Test Cases
}
main();``````

#### input

`````` Given Text : abcaabcccabc
Substring  : abc
Output     : 3
Given Text : coolcool
Substring  : oo
Output     : 2
Given Text : aaaaa
Substring  : aa
Output     : 4
Given Text : aa
Substring  : aa
Output     : 1``````
``````#  Python 3 Program for
#  Count occurrences of a substring recursively
class Occurrences :
#  By using recursion count all possible substrings in given text
def countSubString(self, text, substring, i) :
if (len(text) < len(substring) or i > len(text) - len(substring)) :
#  Stop recursion
return 0

count = 0
#  Compare substring text
while (count < len(substring) and(i + count) < len(text) and
text[i + count] == substring[count]) :
count += 1

if (count == len(substring)) :
#  When substring exist in given text
return 1 + self.countSubString(text, substring, i + 1)

#  When substring not exist then try to check substring with next position
return self.countSubString(text, substring, i + 1)

#  Handles the request to printing calculate result
def countOccurrence(self, text, substring) :
print(" Given Text : ", text)
print(" Substring  : ", substring)
print(" Output     : ", self.countSubString(text, substring, 0))

def main() :
#  Test Cases

if __name__ == "__main__": main()``````

#### input

`````` Given Text :  abcaabcccabc
Substring  :  abc
Output     :  3
Given Text :  coolcool
Substring  :  oo
Output     :  2
Given Text :  aaaaa
Substring  :  aa
Output     :  4
Given Text :  aa
Substring  :  aa
Output     :  1``````
``````#  Ruby Program for
#  Count occurrences of a substring recursively
class Occurrences
#  By using recursion count all possible substrings in given text
def countSubString(text, substring, i)
if (text.length < substring.length ||
i > text.length - substring.length)
#  Stop recursion
return 0
end

count = 0
#  Compare substring text
while (count < substring.length && (i + count) < text.length &&
text[i + count] == substring[count])
count += 1
end

if (count == substring.length)
#  When substring exist in given text
return 1 + self.countSubString(text, substring, i + 1)
end

#  When substring not exist then try to check substring with next position
return self.countSubString(text, substring, i + 1)
end

#  Handles the request to printing calculate result
def countOccurrence(text, substring)
print(" Given Text : ", text, "\n")
print(" Substring  : ", substring, "\n")
print(" Output     : ", self.countSubString(text, substring, 0), "\n")
end

end

def main()
#  Test Cases
end

main()``````

#### input

`````` Given Text : abcaabcccabc
Substring  : abc
Output     : 3
Given Text : coolcool
Substring  : oo
Output     : 2
Given Text : aaaaa
Substring  : aa
Output     : 4
Given Text : aa
Substring  : aa
Output     : 1
``````
``````/*
Scala Program for
Count occurrences of a substring recursively
*/
class Occurrences()
{
// By using recursion count all possible substrings in given text
def countSubString(text: String, substring: String, i: Int): Int = {
if (text.length() < substring.length() ||
i > text.length() - substring.length())
{
// Stop recursion
return 0;
}
var count: Int = 0;
// Compare substring text
while (count < substring.length() && (i + count) < text.length()
&& text.charAt(i + count) == substring.charAt(count))
{
count += 1;
}
if (count == substring.length())
{
// When substring exist in given text
return 1 + countSubString(text, substring, i + 1);
}
// When substring not exist then try to check substring with next position
return countSubString(text, substring, i + 1);
}
// Handles the request to printing calculate result
def countOccurrence(text: String, substring: String): Unit = {
println(" Given Text : " + text);
println(" Substring  : " + substring);
println(" Output     : " + countSubString(text, substring, 0));
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Occurrences = new Occurrences();
// Test Cases
}
}``````

#### input

`````` Given Text : abcaabcccabc
Substring  : abc
Output     : 3
Given Text : coolcool
Substring  : oo
Output     : 2
Given Text : aaaaa
Substring  : aa
Output     : 4
Given Text : aa
Substring  : aa
Output     : 1``````
``````/*
Swift 4 Program for
Count occurrences of a substring recursively
*/
class Occurrences
{
// By using recursion count all possible substrings in given text
func countSubString(_ t: String, _ s: String, _ i: Int)->Int
{
let text = Array(t);
let substring = Array(s);
if (text.count < substring.count || i > text.count - substring.count)
{
// Stop recursion
return 0;
}
var count: Int = 0;
// Compare substring text
while (count < substring.count && (i + count) < text.count &&
text[i + count] == substring[count])
{
count += 1;
}
if (count == substring.count)
{
// When substring exist in given text
return 1 + self.countSubString(t, s, i + 1);
}
// When substring not exist then try to check substring with next position
return self.countSubString(t, s, i + 1);
}
// Handles the request to printing calculate result
func countOccurrence(_ text: String, _ substring: String)
{
print(" Given Text : ", text);
print(" Substring  : ", substring);
print(" Output     : ", self.countSubString(text, substring, 0));
}
}
func main()
{
// Test Cases
}
main();``````

#### input

`````` Given Text :  abcaabcccabc
Substring  :  abc
Output     :  3
Given Text :  coolcool
Substring  :  oo
Output     :  2
Given Text :  aaaaa
Substring  :  aa
Output     :  4
Given Text :  aa
Substring  :  aa
Output     :  1``````
``````/*
Kotlin Program for
Count occurrences of a substring recursively
*/
class Occurrences
{
// By using recursion count all possible substrings in given text
fun countSubString(text: String, substring: String, i: Int): Int
{
if (text.length < substring.length
|| i > text.length - substring.length)
{
// Stop recursion
return 0;
}
var count: Int = 0;
while (count < substring.length && (i + count) < text.length
&& text.get(i + count) == substring.get(count))
{
count += 1;
}
if (count == substring.length)
{
// When substring exist in given text
return 1 + this.countSubString(text, substring, i + 1);
}
// When substring not exist then try to check substring with next position
return this.countSubString(text, substring, i + 1);
}
// Handles the request to printing calculate result
fun countOccurrence(text: String, substring: String): Unit
{
println(" Given Text : " + text);
println(" Substring  : " + substring);
println(" Output     : " + this.countSubString(text, substring, 0));
}
}
fun main(args: Array < String > ): Unit
{
// Test Cases
}``````

#### input

`````` Given Text : abcaabcccabc
Substring  : abc
Output     : 3
Given Text : coolcool
Substring  : oo
Output     : 2
Given Text : aaaaa
Substring  : aa
Output     : 4
Given Text : aa
Substring  : aa
Output     : 1``````

## Output Explanation

The code demonstrates the counting of occurrences of a substring within a given text using recursion. The output shows the text, substring, and the count of occurrences.

## Time Complexity

The time complexity of this algorithm is O(n * m), where n is the length of the text and m is the length of the substring. This is because in the worst case, for each character in the text, we might need to check m characters for a match with the substring.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post