Последовательное точное сравнение строк: различия между версиями

Поиск можно осуществить с использованием реализованного детерминированного конечного автомата с поиском потомка по умолчанию <math>\mathcal{D}(P)</math>, распознающего язык <math>\Sigma * P</math>. Размер реализации алгоритма составляет O(m) и не зависит от размера алфавита в силу того, что автомат <math>\mathcal{D}(P)</math> имеет m + 1 состояний, m прямых дуг и не более m обратных дуг. Использование конечного автомата для поиска в тексте позволяет получить алгоритм с эффективной задержкой (представляющей собой максимальное время обработки символа текста).

[https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D0%B9%D0%B5%D1%80%D0%B0_%E2%80%94_%D0%9C%D1%83%D1%80%D0%B0| Алгоритм Бойера-Мура] считается одним из самых эффективных алгоритмов решения задачи ESM. Его упрощенная версия либо весь алгоритм полностью нередко применяется в программах редактирования текстов для выполнения операций поиска и замены.

'''Теорема 5 (Коул, 1994 [5, 14]). В ходе поиска непериодического шаблона P длины m (такой, что длина самой длинной границы P меньше m/2) в тексте T длины n алгоритм Бойера-Мура производит не более 3n сравнений между буквами P и T.'''