Ta strona o algorytmie Knuth-Moriss-Pratt w porównaniu do Boyera-Moore'a opisuje możliwy przypadek, w którym algorytm Boyera-Moore'a cierpi z powodu małej odległości pominięcia, podczas gdy KMP może działać lepiej.
Szukam dobrego przykładu (tekst, wzór), który może jasno zademonstrować ten przypadek.
10
Odpowiedzi:
Istnieje artykuł, który przeprowadził dobry eksperyment nad tymi algorytmami dopasowywania ciągów dla różnych wzorców: „ Porównanie algorytmów dopasowywania ciągów: pomoc w zabezpieczeniu zawartości informacyjnej ”
Istnieje również analiza tych algorytmów dopasowania łańcucha dla języka japońskiego: Porównanie i ulepszenie algorytmów dopasowania łańcucha dla tekstów japońskich
Mam nadzieję, że są one przydatne, aby dowiedzieć się o wydajności algorytmów!
źródło
Te wzorce przyspieszą działanie KMP:
T = aaaaaaaaaa P = aaaa KMP spróbuje 10 porównać kroki, w których Boyer-Moore podejmie 28
Inny przykład:
T = aaaaaaaaaa P = abab KMP spróbuje wykonać 8 kroków porównania, w których BM spróbuje 12.
źródło