Frecuencia de una substring en una string | conjunto 2

Dada una string str de longitud N y un patrón de substring de longitud M , la tarea es encontrar la frecuencia de aparición del patrón como una substring en la string dada. Si el patrón está presente en la string str , imprima » Sí » con el recuento de su aparición. De lo contrario, escriba “No” .

Ejemplos:

Entrada: str = “geeksforgeeks”, patrón = “geeks”
Salida: 2
Explicación:
La ocurrencia de la string “geeks” en la string “geeksforgeeks” está en el índice 0 y 8.
Por lo tanto, el conteo es 2.

Entrada: str = «dhimanman», patrón = «max»
Salida: 0

Enfoque ingenuo: consulte la publicación anterior para conocer el enfoque más simple para resolver el problema.
Complejidad temporal: O(N*M)
Espacio auxiliar: O(1)

Enfoque usando el algoritmo KMP: consulte la publicación anterior de este artículo para resolver el problema usando el algoritmo KMP .
Complejidad temporal: O(N + M)
Espacio auxiliar: O(M)

Enfoque usando la expresión regular : siga los pasos a continuación para resolver el problema:

• Forme la expresión regular del patrón de string usando la función regex() .
• Crea un smatch M usando la función smatch() .
• Compruebe la presencia del patrón de string en la string str usando la función regex_match() como:

regex_search(str, m, c)
donde,
str es la string dada,
m es smatch,
c es la expresión regular del patrón de string.

• En los pasos anteriores, si la función regex_match() devuelve True , imprima «Sí» y encuentre la aparición del patrón de string . De lo contrario, escriba “No” .
• Cree una variable numberOfMatches del tipo de datos ptrdiff_t para almacenar el recuento de ocurrencias.
• Encuentre el número de coincidencias  usando la función regex_iterator () como:

ptrdiff_t númeroDeCoincidencias = std::distance(sregex_iterator(S.begin(), S.end(), c), sregex_iterator())

• Imprima el recuento de ocurrencias en los pasos anteriores como resultado.

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

// C++ program for the above approach
  
#include <bits/stdc++.h>
using namespace std;
  
// Function to find the frequency of
// substring in the given string S
void find_frequency(string S,
                    string pattern)
{
    // Create a regular expression
    // of the string pattern
    regex c(pattern);
  
    // Determines the matching behavior
    smatch m;
  
    // Use member function on 'm'
    // regex_search to check if
    // string X is present in S or not
    if (regex_search(S, m, c) == true) {
        cout << "Yes"
             << "\n";
    }
    else {
        cout << "No";
    }
  
    // Count the number of matches
    ptrdiff_t numberOfMatches
        = std::distance(
            sregex_iterator(S.begin(),
                            S.end(), c),
            sregex_iterator());
  
    // Print the coun of occurrence
    cout << "Frequency of string "
         << pattern << " is "
         << numberOfMatches;
}
// Driver code
int32_t main()
{
    // Given string str and pattern
    string str = "geeksforgeeks";
    string pattern = "geeks";
  
    // Function Call
    find_frequency(str, pattern);
  
    return 0;
}

Yes
Frequency of string geeks is 2

Complejidad temporal: O(N + M)
Espacio auxiliar: O(M)