Cuente las ocurrencias de una substring recursivamente

Dadas dos strings str1 y str2 , la tarea es contar el número de veces que str2 ocurre en str1 usando recursividad.

Ejemplos: 

Entrada: str1 = «geeksforgeeks», str2 = «geek»
Salida: 2
Explicación: las ocurrencias de str2 en str1 comienzan en el índice {0, 8}

Entrada: str1 = “aaaa”, str2 = “aaa”
Salida : 3
Explicación: Las ocurrencias de str2 en str1 comienzan en el índice {0,1,2

Enfoque: Ya hemos discutido otros enfoques en nuestro artículo anterior, pero aquí vamos a resolver este problema usando la recursividad.

Algoritmo: 

• Si el tamaño de la string str2 es mayor que la string str1 o el tamaño de la string str1 es 0 , entonces devuelve 0 .
• De lo contrario, compruebe si la string str2 está presente en str1 como substring o no.
  • si está presente, incremente el conteo de ocurrencias y llame recursivamente a otra substring .
  • de lo contrario, llame recursivamente a otra substring.
  • devuelve el recuento de cada llamada recursiva como respuesta.

A continuación se muestra la implementación del enfoque anterior:

// 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 = "geeksforgeeks", str2 = "geeks";
    cout << countSubstring(str1, str2) << endl;
   
      str1 = "aaaaa", str2 = "aaa";
    cout << countSubstring(str1, str2) << endl;
 
    return 0;
}

// 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 = "geeksforgeeks",
           str2 = "geeks";
    System.out.println(countSubstring(str1,
                                     str2));
 
    str1 = "aaaaa";
    str2 = "aaa";
    System.out.println(countSubstring(str1,
                                     str2));
 
}
}
 
// This code is contributed
// by Arnab Kundu

# 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 = "geeksforgeeks";
    str2 = "geeks";
    print(countSubstring(str1, str2));
 
    str1 = "aaaaa";
    str2 = "aaa";
    print(countSubstring(str1, str2));
 
# This code is contributed by Princi Singh

// 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 = "geeksforgeeks",
           str2 = "geeks";
    Console.Write(countSubstring(str1,
                                str2));
    Console.Write("\n");
     
    str1 = "aaaaa";
    str2 = "aaa";
    Console.Write(countSubstring(str1,
                                str2));
 
}
}
 
// This code is contributed
// by Smita

<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 = "geeksforgeeks", str2 = "geeks";
document.write( countSubstring(str1, str2),'<br>');
str1 = "aaaaa", str2 = "aaa";
document.write( countSubstring(str1, str2),'<br>');
 
 
</script>

2
3

Complejidad de tiempo: O(N ² ) , (es decir, N es la longitud máxima entre str1 y str2)
Espacio auxiliar:O(1)