1632
правки
Изменения
м
Подстрока{{Задача|definition = Дан текст <tex>t[0 \,\mathinner{\ldotp\ldotp}\, n-1]</tex> и паттерн <tex>p[0 \,\mathinner{\ldotp\ldotp}\, m-1]</tex> такие, что <tex>n \geqslant m</tex> и элементы этих строк {{---}} символы из конечного алфавита <tex> \Sigma </tex>. Требуется проверить, входит ли паттерн <tex>p</tex> в текст <tex>t</tex>.}}{{Определение|definition = Будем говорить, что паттерн <tex>p</tex> встречается в тексте <tex>t</tex> со сдвигом <tex>s</tex>, если <tex> 0 \leqslant s \leqslant n-m</tex> и <tex>t[s \,\mathinner{\ldotp\ldotp}\, s + m - 1] = p</tex>. Если строка <tex>p</tex> встречается в строке <tex>t</tex>, то <tex>p</tex> является подстрокой <tex>t</tex>. }} ==Алгоритм==В наивном алгоритме поиск всех допустимых сдвигов производится с помощью цикла, в котором проверяется условие<tex>t[s \,\mathinner{\ldotp\ldotp}\, s + m - 1] = p</tex> для каждого из <tex> n - m + 1 </tex> возможных значений <tex>s</tex>. ===Псевдокод===Приведем пример псевдокода, который находит все вхождения строки <tex>p</tex> в <tex>t</tex> и возвращает массив позиций, откуда начинаются вхождения. '''vector<int>''' naiveStringMatcher(t : '''string''', p : '''string'''): '''int''' n = t.length '''int''' m = p.length '''vector<int>''' ans '''for''' i = 0 '''to''' n - m '''if''' t[i .. i + m - 1] == p ans.push_back(i) '''return''' ans ===Время работы===Алгоритм работает за <tex>O(m \cdot (n - m))</tex>. В худшем случае <tex> m = </tex> <tex>\dfrac{n}{2}</tex>, что даёт <tex> O\left(\dfrac{n^2}{4}\right) = O\left(n^2\right) </tex>.Однако если <tex>m</tex> достаточно мало по сравнению с <tex>n</tex>, то тогда асимптотика получается близкой к <tex>O(n)</tex>, поэтому этот алгоритм достаточно широко применяется на практике. == Сравнение с другими алгоритмами ===== Преимущества ===* Требует <tex>O(1)</tex> памяти.* Приемлемое время работы на практике (см. выше). Благодаря этом алгоритм применяется, например, в браузерах и текстовых редакторах (при использовании <tt>Ctrl + F</tt>), потому что обычно паттерн, который нужно найти, очень короткий по сравнению с самим текстом. Также наивный алгоритм используется в стандартных библиотеках языков высокого уровня (C++, Java), потому что он не требует дополнительной памяти.* Простая и понятная реализация.=== Недостатки ===* Требует <tex>O(m \cdot (n-m))</tex> операций, вследствие чего алгоритм работает медленно в случае, когда длина паттерна достаточно велика (см. выше). == Источники информации ==* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 3-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2014. — 1328 с.: ил. — ISBN 978-5-8459-1794-2 (рус.) — страница 1034. [[Категория:Алгоритмы и структуры данных]][[Категория:Поиск подстроки в строке]][[Категория:Точный поиск]]
rollbackEdits.php mass rollback
