¿Un ejemplo donde el algoritmo Knuth-Morris-Pratt es más rápido que Boyer-Moore?

10

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.

Erb
fuente
SO stackoverflow.com/questions/12656160/…
Ciro Santilli 冠状 病毒 审查 六四 事件 法轮功

Respuestas:

3

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!

Reza
fuente
3

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.

Erb
fuente
En el primer ejemplo, ambos algoritmos encontrarán una coincidencia inmediatamente, en el primer turno: ¿cómo harían más de 4 comparaciones?
BartoszKP