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:
    task = new Occurrences()
    task.countOccurrence("abcaabcccabc", "abc")
    task.countOccurrence("coolcool", "oo")
    task.countOccurrence("aaaaa", "aa")
    task.countOccurrence("aa", "aa")

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)
    {
        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.

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.

New Comment





Categories
Relative Post