130
правок
Изменения
Тикет 2-1
{{Задача|definition ==Постановка задачи==Дан текст <tex>t[1 {} .. {} n]</tex> и паттерн <tex>p[1 .. m]</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 + 1 .. s + m] = p[1..m].</tex> Если строка <tex>p</tex> встречается в строке <tex>t</tex>, то <tex>p</tex> является подстрокой <tex>t</tex>. Требуется проверить, входит ли паттерн <tex>p</tex> в текст <tex>t</tex>.}}
==Алгоритм==
В наивном алгоритме поиск всех допустимых сдвигов производится с помощью цикла, в котором проверяется условие <tex>t[s + 1 .. s + m] = p[1..m] </tex> для каждого из <tex> n - m + 1 </tex> возможных значений <tex>s</tex>.
===Псевдокод===
Приведем пример псевдокода, который находит все вхождения строки <tex>p</tex> в <tex>t</tex> и возвращает массив позиций, откуда начинаются вхождения.
'''vector<int>''' naiveStringMatcher('''string''' t, '''string''' p):
'''return''' ans
===Время работы===
Алгоритм работает за <tex>O(m \cdot (n - m))</tex>. В худшем случае <tex> m = </tex> <tex dpi ="150"> \frac{n}{2}, </tex> что дает <tex> O(n^2/4) = O(n^2) </tex>.
Однако если <tex>m</tex> достаточно мало, по сравнению с <tex>n</tex>, то тогда асимптотика получается близкой к <tex>O(n)</tex>, поэтому этот алгоритм достаточно широко применяется на практике.
==Преимущества==
*Требует <tex>O(1)</tex> памяти.*Простая и понятная реализацияПриемлемое время работы на практике (см.*Если <tex>m</tex> достаточно мало, по сравнению с <tex>n</tex>, то тогда асимптотика получается близкой к <tex>O(nвыше)</tex>. Поэтому этот Благодаря этом алгоритм активно используется применяется, например, в браузерах и текстовых редакторах (при использовании <tex> \mathrm{Ctrl} \texttt{+} \mathrm{F}</tex>), потому что обычно паттерн, который нужно найти очень короткий по сравнению с самим текстом. Также наивный алгоритм используется в стандартных библиотеках языков высокого уровня <tex>(\mathrm{C}\texttt{++},\ \mathrm{Java})</tex>, потому что он не требует дополнительной памяти.* Простая и понятная реализация.
== Литература Источники информации ==
* ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ.[http://wmate.ru/ebooks/?dl=380&mirror=1] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Поиск подстроки в строке]]
