Algoritmo de búsqueda de cadenas Boyer-Moore

Generalmente el algoritmo es más rápido cuanto más grande es la clave que es buscada, usa la información conseguida desde un intento para descartar tantas posiciones del texto como sean posibles en donde la cadena no coincida.A la gente frecuentemente le sorprende el algoritmo de Boyer-Moore, cuando lo conoce, porque en su verificación intenta comprobar si hay una coincidencia en una posición particular marchando hacia atrás.La razón por la que Boyer-Moore elige este enfoque está más clara cuando consideramos que pasa si la verficación falla-por ejemplo, si en lugar de una "N" en la octava posición, encontramos una "X".La "X" no aparece en "ANPANMAN", y esto significa que no hay coincidencia para la cadena buscada en el inicio del texto-o en las siguientes siete posiciones, puesto que todas fallarían también con la "X".Esto también explica el resultado algo contra-intuitivo de que cuanto más largo es el patrón que estamos buscando, el algoritmo suele ser más rápido para encontrarlo.El algoritmo precalcula dos tablas para procesar la información que obtiene en cada verificación fallada: una tabla calcula cuantas posiciones hay por delante en la siguiente búsqueda basada en el valor del carácter que no coincide; la otra hace un cálculo similar basado en cuantos caracteres coincidieron satisfactoriamente antes del intento de coincidencia fallado.Para cada i menor que la longitud de la cadena de búsqueda, constrúyase el patrón consistente en los últimos i caracteres de la cadena precedida por un carácter no-coincidente, alinéense a la derecha el patrón y la cadena, y anótese el menor número de caracteres para que el patrón tenga que desplazarse a la izquierda para una coincidencia.Por ejemplo, para la búsqueda de la cadena ANPANMAN, la tabla sería como sigue: (NMAN significa una subcadena en ANPANMAN consistente en un carácter que no es 'N' más los caracteres 'MAN'.)Esto es a veces llamado "regla del sufijo bueno débil" y no es suficiente para conseguir que Boyer-Moore funcione en tiempo lineal en el peor caso.Cada vez que usted se mueve a la izquierda, si el carácter sobre el que está no está ya en la tabla, añádalo; su valor de desplazamiento es la distancia desde el carácter más a la derecha.Ejemplo: Para la cadena ANPANMAN, la segunda tabla sería como se muestra (por claridad, las entradas son mostradas en el orden que serían añadidas a la tabla): (La N que se supuestamente sería cero está basada en la segunda N desde la derecha porque solo anotamos el cálculo para las primeras[2]​ El caso peor para encontrar todas las coincidencias en un texto necesita aproximadamente, a pesar de que el texto contenga una coincidencia o no.El Algoritmo Boyer-Moore Turbo toma una cantidad constante adicional de espacio para completar una búsqueda encomparaciones, mientras que el algoritmo Boyer-Moore requiere (en el peor caso) tan solo