Последовательное точное сравнение строк: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 30: | Строка 30: | ||
'''Теорема 3 (Кнут, Моррис и Пратт, 1977 [11])). Текстовый поиск может быть выполнен за время O(n) с использованием памяти в размере O(m). Предварительная обработка образца может быть выполнена за время O(m).''' | '''Теорема 3 (Кнут, Моррис и Пратт, 1977 [11])). Текстовый поиск может быть выполнен за время O(n) с использованием памяти в размере O(m). Предварительная обработка образца может быть выполнена за время O(m).''' | ||
Поиск можно реализовать с использованием реализованного алгоритма поиска потомка по умолчанию из детерминированного конечного автомата D(P), распознающего язык S*P. Размер реализации алгоритма составляет O(m) и не зависит от размера алфавита в силу того, что автомат D(P) имеет m + 1 состояний, m прямых дуг и не более m обратных дуг. Использование конечного автомата для поиска в тексте позволяет получить алгоритм с эффективной задержкой (представляющей собой максимальное время обработки символа текста). | |||
'''Теорема 4 (Ханкарт, 1993 [ ]). Поиск образца P может быть произведен с задержкой в O(min{a, log2 m)g) сравнений букв.''' | |||
Заметим, что в большинстве алгоритмов предварительная обработка образца не обязательно производится перед разбором текста, поскольку ее можно выполнить «на лету» в процессе разбора. | |||
'''Практически эффективные алгоритмы''' | |||
Алгоритм Бойера-Мура считается одним из самых эффективных алгоритмов решения задачи ESM. Его упрощенная версия либо весь алгоритм полностью нередко применяется в программах редактирования текстов для выполнения операций поиска и замены. | |||