Эта страница, посвященная алгоритму Кнута-Мориса-Пратта по сравнению с Бойером-Муром, описывает возможный случай, когда алгоритм Бойера-Мура страдает небольшим пропуском, а KMP может работать лучше.
Я ищу хороший пример (текст, шаблон), который может четко продемонстрировать этот случай.
10
Ответы:
Есть статья, в которой был проведен хороший эксперимент над этими алгоритмами сопоставления строк для различных шаблонов: « Сравнение алгоритмов сопоставления строк: помощь в защите информационного контента »
Также изучаются алгоритмы сопоставления строк для японского языка: сравнение и улучшение алгоритмов сопоставления строк для японских текстов.
Я надеюсь, что они полезны, чтобы понять эффективность алгоритмов!
источник
Эти шаблоны позволят KMP работать быстрее:
T = aaaaaaaaaa P = aaaa KMP попробует 10 сравнительных шагов, где Бойер-Мур сделает 28
Другой пример:
T = aaaaaaaaaa P = abab KMP попробует 8 сравнительных шагов, где BM попробует 12.
источник