Halaman ini tentang Algoritma Knuth-Moriss-Pratt dibandingkan dengan Boyer-Moore menjelaskan kemungkinan kasus di mana algoritma Boyer-Moore menderita dari jarak lompatan kecil sementara KMP dapat bekerja lebih baik.
Saya mencari contoh yang bagus (teks, pola) yang dapat dengan jelas menunjukkan kasus ini.
10
Jawaban:
Ada makalah yang melakukan percobaan yang baik atas algoritma pencocokan string ini untuk pola yang berbeda: " Perbandingan algoritma pencocokan string: bantuan untuk keamanan konten informasi "
Juga ada studi tentang algoritma pencocokan string ini untuk bahasa Jepang: Perbandingan dan Peningkatan Algoritma Pencocokan String Untuk Teks Jepang
Saya harap ini berguna untuk memahami efisiensi algoritma!
sumber
Pola-pola ini akan membuat KMP bekerja lebih cepat:
T = aaaaaaaaaa P = aaaa KMP akan mencoba 10 langkah pembandingan dimana Boyer-Moore akan mengambil 28
Contoh lain:
T = aaaaaaaaaa P = abab KMP akan mencoba 8 membandingkan langkah-langkah di mana BM akan mencoba 12.
sumber