Algoritmos de búsqueda, Búsqueda sencilla de strings (Naive string search)

¿Cómo funciona el algoritmo de búsqueda sencilla de strings?

El algoritmo de búsqueda sencilla de strings (Naive string search) es la forma mas básica y a la vez ineficiente de buscar cadenas de texto dentro de un string.

Supongamos que se desea contar el numero de veces que un string aparece dentro de otro.

Una solución inmediata es verificar pares de caracteres individualmente a través de toda la cadena larga.

Pasos a ejecutar en el algoritmo de búsqueda sencilla de strings.

  1. Recorre el string mas largo.
  2. Recorre el string menor.
  3. Si los caracteres no coinciden, inicia nuevamente el segundo loop.
  4. Si los caracteres coinciden continua con la iteración.
  5. Si se completa el loop incrementa el contador a 1 y reinicia la segunda iteración.

Ejemplo.

Escriba una función que cuente el número de veces que aparece un string dentro de otro.

function contarCoincidenciasEnCadena(cadena, subcadena) {
    let coincidencias = 0;

    for (let i = 0; i < cadena.length; i++) {
        for (let j = 0; j < subcadena.length; j++) {
            if (subcadena[j] !== cadena[i + j]) {
                break;
            }
            if (j === subcadena.length - 1) {
                coincidencias++;
            }
        }
    }

    return coincidencias;
}