Esta página sobre el algoritmo de Knuth-Moriss-Pratt en comparación con Boyer-Moore describe un posible caso en el que el algoritmo de Boyer-Moore sufre una pequeña distancia de salto mientras que KMP podría funcionar mejor.
Estoy buscando un buen ejemplo (texto, patrón) que pueda demostrar claramente este caso.
10
Respuestas:
Hay un documento que hizo un buen experimento sobre estos algoritmos de coincidencia de cadenas para diferentes patrones: " Comparación de algoritmos de coincidencia de cadenas: una ayuda para la seguridad del contenido de la información "
También hay un estudio de estos algoritmos de coincidencia de cadenas para el idioma japonés: Comparación y mejora de los algoritmos de coincidencia de cadenas para textos japoneses
¡Espero que sean útiles para tener una idea de la eficiencia de los algoritmos!
fuente
Bueno, estos patrones harán que KMP funcione más rápido:
T = aaaaaaaaaa P = aaaa KMP intentará 10 pasos de comparación donde Boyer-Moore tomará 28
Otro ejemplo:
T = aaaaaaaaaa P = abab KMP intentará 8 pasos de comparación donde BM intentará 12.
fuente