как оптимизировать алгоритм сопоставления строк Кнута Морриса Пратта

Question

если мы обнаружили несоответствие, можем ли мы предположить, что следующий символ в тексте является несоответствием или нет без сравнения,

text: abacabba

pattern: abba

теперь, когда он сравнивает 2-е «b» в шаблоне с 2-м «a» в тексте, возникает несоответствие, есть ли способ избежать «c», заменяющего «a», потому что это тоже будет несоответствие.и как KMP работает с текстом и шаблоном, указанными ниже

text: aaaaaaa

pattern: aa

Answer 1

Если вы хотите пропустить сравнения в тексте для повышения эффективности, вам следует воспользоваться Алгоритмом Бойера-Мура , который сравнивает справа налево. Он может иметь наилучшее время выполненияΩ (н / м) и наихудший случай O (n).Ω (н / м) возникает в результате прогнозирования и пропуска бесполезных сравнений.

алгоритм Кнута Морриса Пратта выполняет сравнения слева направо, в которых нетспособ узнать следующие символы, и таблица префиксов KMP также передает информацию только о шаблоне.

Вы могли бы даже рассмотреть алгоритм Бойера Мура Хорспула , который имеет лучшую асимптотику, чемБойера Мура (при больших размерах рисунков).

Подробные графики моделирования всех основных алгоритмов поиска строк можно посмотреть здесь здесь .

Answer 2

Я думаю, что алгоритм Horspool - это то, что вы ищете. Потому что когда есть соответствующий символ, которого нет в паттерне, он сразу же перепрыгнет через эту часть. И остальная часть шаблона больше не будет сравниваться с этим символом.