Algoritmo Fuerza Bruta


Características

  • Es el algoritmo más simple posible.
  • Consiste en probar todas las posibles posiciones del patrón en el texto.
  • Requiere espacio constante.
  • Realiza siempre saltos de un carácter.
  • Compara de izquierda a derecha.
  • Realiza la búsqueda del patrón en un tiempo O(mn).
  • Realiza 2n comparaciones previstas de los caracteres del texto.

Lógica

  • Se sitúa el patrón en la primera posición, y se compara carácter a carácter hasta encontrar un fallo o llegar al final del patrón.
  • Se pasa a la siguiente posición y se repite el proceso.
  • El proceso finaliza al alcanzar el final del texto
  • No existe un preprocesamiento del patrón.

Descripción

  • No requiere ninguna fase de preproceso previo, ni un espacio extra constante además del espacio asignado al patrón y al texto.
  • Para la búsqueda:
    • Consiste en la comparación de todas las posiciones del texto entre 0 y el n-m, si una ocurrencia del patrón corresponde o no.
    • Si encuentra una no ocurrencia, o una ocurrencia total del patrón, salta un carácter hacia la derecha.

Ejemplo

Se alinea la primera posición del patrón con la primera posición del texto, y se comparan los caracteres uno a uno hasta que se acabe el patrón, esto es, se encontró una ocurrencia del patrón en el texto, o hasta que se encuentre una discrepancia.



Si se detiene la búsqueda por una discrepancia, se desliza el patrón en una posición hacia la derecha y se intenta calzar el patrón nuevamente.




Subpages (1): Ejemplo
Comments