Skip to main content

Count occurrences of a substring recursively

Counting occurrences of a substring recursively means finding the number of times a particular substring appears within a larger string, and repeating the process for all the substrings that are present in the original string. This process is performed recursively until there are no more occurrences of the substring left to count.

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
Last updated on by Kalkicode




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