Algoritmo Fuerza Bruta

[pic 1]ESCUELA POLITÉCNICA NACIONAL[pic 2]

ESTRUCTURA DE DATOS Y ALGORITMOS II

GR1ISW

ESCUELA POLITÉCNICA NACIONAL

INGENIERÍA EN SOFTWARE  

ESTRUCTURA DE DATOS Y ALGORITMOS II

ALGORITMO FUERZA BRUTA

Integrantes:         

Fecha:                 

20 de enero de 2022

TABLA DE CONTENIDOS

OBJETIVO        1

MARCO TEÓRICO        1

IMPLEMENTACIÓN        2

EJECUCIÓN        2

REFERENCIAS        3

OBJETIVO

1. Comprender la importancia de los algoritmos de búsqueda de patrones en un texto determinado.
2. Implementar y ejecutar el algoritmo de fuerza bruta en lenguaje Java.

MARCO TEÓRICO

El algoritmo de Fuerza Bruta consiste en comparar carácter a carácter el patrón que se quiere buscar y la subcadena del texto que se considera en cada caso. Para ello chequea todas las subcadenas del texto de tamaño m. Si se encuentra una ocurrencia del patrón en el texto con menos discrepancias de las permitidas, se devuelve como resultado. Tras cada comparación se mueve el índice del texto una posición a la derecha.

Puede optimizarse esta versión de forma que si se supera el número de discrepancias permitidas también se mueve el índice del texto una posición a la derecha.

Este algoritmo no requiere preprocesado ni espacio extra en memoria.

IMPLEMENTACIÓN

package com.company;

public class Main2 {
       public static void main(String[] args) {
           String string = "ABCABAB ABABABAABAC";
           String pattern = "ABABAABA";

           stringSearch(string, pattern);
       }
       private static void stringSearch(String string, String pattern) {
           int sLen = string.length();
           int pLen = pattern.length();
           boolean found = false;
           int i;
           for(i = 0; i < sLen - pLen + 1; i++) {
               int j = 0;
               for (; j < pLen; j++) {
                   if (string.charAt(i + j) != pattern.charAt(j))
                       break;
               }
               if (j == pLen) {
                   found = true;
                   break;
               }
           }
           if (found) {
               System.out.println("Se encuentra el patrón en el índice: " + i);
           } else {
               System.out.println("No se encontro en el patrón");
           }
       }
}

...