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:
task = new Occurrences()
task.countOccurrence("abcaabcccabc", "abc")
task.countOccurrence("coolcool", "oo")
task.countOccurrence("aaaaa", "aa")
task.countOccurrence("aa", "aa")
Algorithm Explanation
- Create a recursive function
countSubString
that takes thetext
,substring
, and an indexi
as arguments. - Inside the function, check if the length of the remaining portion of the
text
is less than the length of thesubstring
, or ifi
exceeds the valid index range. - If either condition is met, return 0 to stop the recursion.
- Initialize a variable
count
to 0. - Use a loop to compare the characters of the
substring
andtext
starting from indexi
. Incrementcount
for each matching character. - If
count
reaches the length of thesubstring
, it means a complete match is found, so increment the count and make a recursive call tocountSubString
with the next index. - If no match is found, continue the recursion by calling
countSubString
with the next index. - 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)
{
Occurrences task = new Occurrences();
// Test Cases
task.countOccurrence("abcaabcccabc", "abc");
task.countOccurrence("coolcool", "oo");
task.countOccurrence("aaaaa", "aa");
task.countOccurrence("aa", "aa");
}
}
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()
{
Occurrences *task = new Occurrences();
// Test Cases
task->countOccurrence("abcaabcccabc", "abc");
task->countOccurrence("coolcool", "oo");
task->countOccurrence("aaaaa", "aa");
task->countOccurrence("aa", "aa");
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)
{
Occurrences task = new Occurrences();
// Test Cases
task.countOccurrence("abcaabcccabc", "abc");
task.countOccurrence("coolcool", "oo");
task.countOccurrence("aaaaa", "aa");
task.countOccurrence("aa", "aa");
}
}
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()
{
$task = new Occurrences();
// Test Cases
$task->countOccurrence("abcaabcccabc", "abc");
$task->countOccurrence("coolcool", "oo");
$task->countOccurrence("aaaaa", "aa");
$task->countOccurrence("aa", "aa");
}
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()
{
var task = new Occurrences();
// Test Cases
task.countOccurrence("abcaabcccabc", "abc");
task.countOccurrence("coolcool", "oo");
task.countOccurrence("aaaaa", "aa");
task.countOccurrence("aa", "aa");
}
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() :
task = Occurrences()
# Test Cases
task.countOccurrence("abcaabcccabc", "abc")
task.countOccurrence("coolcool", "oo")
task.countOccurrence("aaaaa", "aa")
task.countOccurrence("aa", "aa")
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()
task = Occurrences.new()
# Test Cases
task.countOccurrence("abcaabcccabc", "abc")
task.countOccurrence("coolcool", "oo")
task.countOccurrence("aaaaa", "aa")
task.countOccurrence("aa", "aa")
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
task.countOccurrence("abcaabcccabc", "abc");
task.countOccurrence("coolcool", "oo");
task.countOccurrence("aaaaa", "aa");
task.countOccurrence("aa", "aa");
}
}
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()
{
let task: Occurrences = Occurrences();
// Test Cases
task.countOccurrence("abcaabcccabc", "abc");
task.countOccurrence("coolcool", "oo");
task.countOccurrence("aaaaa", "aa");
task.countOccurrence("aa", "aa");
}
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
{
val task: Occurrences = Occurrences();
// Test Cases
task.countOccurrence("abcaabcccabc", "abc");
task.countOccurrence("coolcool", "oo");
task.countOccurrence("aaaaa", "aa");
task.countOccurrence("aa", "aa");
}
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.
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.
New Comment