Esta página sobre o algoritmo de Knuth-Moriss-Pratt em comparação com Boyer-Moore descreve um possível caso em que o algoritmo de Boyer-Moore sofre com uma pequena distância de salto, enquanto o KMP pode ter um desempenho melhor.
Estou procurando um bom exemplo (texto, padrão) que possa demonstrar claramente esse caso.
10
Respostas:
Há um artigo que fez um bom experimento sobre esses algoritmos de correspondência de strings para diferentes padrões: " Comparação de algoritmos de correspondência de strings: uma ajuda à segurança do conteúdo da informação "
Também há um estudo desses algoritmos de correspondência de strings para o idioma japonês: Comparação e aprimoramento de algoritmos de correspondência de strings para textos em japonês
Espero que sejam úteis para entender a eficiência dos algoritmos!
fonte
Bem, esses padrões farão o KMP funcionar mais rápido:
T = aaaaaaaaaa P = aaaa O KMP tentará 10 etapas de comparação onde Boyer-Moore levará 28
Outro exemplo:
T = aaaaaaaaaa P = abab O KMP tentará 8 comparar as etapas em que BM tentará 12.
fonte