4551
правка
Последовательное точное сравнение строк: различия между версиями
Перейти к навигации
Перейти к поиску
Последовательное точное сравнение строк (посмотреть исходный код)
Версия от 15:18, 23 апреля 2019
, 23 апреля 2019→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 32: | Строка 32: | ||
Поиск можно | Поиск можно осуществить с использованием реализованного алгоритма поиска потомка по умолчанию из детерминированного конечного автомата <math>\mathcal{D}(P)</math>, распознающего язык <math>\Sigma * P</math>. Размер реализации алгоритма составляет O(m) и не зависит от размера алфавита в силу того, что автомат <math>\mathcal{D}(P)</math> имеет m + 1 состояний, m прямых дуг и не более m обратных дуг. Использование конечного автомата для поиска в тексте позволяет получить алгоритм с эффективной задержкой (представляющей собой максимальное время обработки символа текста). | ||
'''Теорема 4 (Ханкарт, 1993 [ ]). Поиск образца P может быть произведен с задержкой в O(min{ | '''Теорема 4 (Ханкарт, 1993 [10]). Поиск образца P может быть произведен с задержкой в <math>O(min \{ \sigma, log_2 \; m ) \} )</math> сравнений букв.''' | ||
| Строка 43: | Строка 43: | ||
'''Практически эффективные алгоритмы''' | '''Практически эффективные алгоритмы''' | ||
Алгоритм Бойера-Мура считается одним из самых эффективных алгоритмов решения задачи ESM. Его упрощенная версия либо весь алгоритм полностью нередко применяется в программах редактирования текстов для выполнения операций поиска и замены. | [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. Его упрощенная версия либо весь алгоритм полностью нередко применяется в программах редактирования текстов для выполнения операций поиска и замены. | ||