Пример, где алгоритм Кнута-Морриса-Пратта работает быстрее, чем Бойер-Мур?

10

Эта страница, посвященная алгоритму Кнута-Мориса-Пратта по сравнению с Бойером-Муром, описывает возможный случай, когда алгоритм Бойера-Мура страдает небольшим пропуском, а KMP может работать лучше.
Я ищу хороший пример (текст, шаблон), который может четко продемонстрировать этот случай.

эрб
источник
ТАК stackoverflow.com/questions/12656160/…
Сиро Сантилли 冠状 病毒 审查 六四 事件 法轮功

Ответы:

3

Есть статья, в которой был проведен хороший эксперимент над этими алгоритмами сопоставления строк для различных шаблонов: « Сравнение алгоритмов сопоставления строк: помощь в защите информационного контента »

Также изучаются алгоритмы сопоставления строк для японского языка: сравнение и улучшение алгоритмов сопоставления строк для японских текстов.

Я надеюсь, что они полезны, чтобы понять эффективность алгоритмов!

Реза
источник
3

Эти шаблоны позволят KMP работать быстрее:

T = aaaaaaaaaa P = aaaa KMP попробует 10 сравнительных шагов, где Бойер-Мур сделает 28

Другой пример:

T = aaaaaaaaaa P = abab KMP попробует 8 сравнительных шагов, где BM попробует 12.

эрб
источник
В первом примере оба алгоритма найдут совпадение сразу, при первой смене - как они будут делать более 4 сравнений?
BartoszKP