Изменения

{{Задача|definition ==Постановка задачи==Имеются строки Дан текст <tex>t[0 \,\mathinner{\ldotp\ldotp}\, n-1 .. n]</tex> и паттерн <tex>p[0 \,\mathinner{\ldotp\ldotp}\, m-1 .. m]</tex> такие, что <tex>n</tex> <tex>\ge</tex> <tex>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 .. \,\mathinner{\ldotp\ldotp}\, s + m- 1] = 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 .. \,\mathinner{\ldotp\ldotp}\, s + m- 1] = p[1..m] </tex> для каждого из <tex> n - m + 1 </tex> возможных значений <tex>s</tex>.

===Псевдокод===

'''vector<int>''' naiveStringMatcher (t : '''string''' t, p : '''string''' p):

'''for''' i = 1 .. 0 '''to''' n - m + 1 '''if''' (t[i] == p[1]) '''and''' (t[i + 1] == p[2]) .. '''and''' (t[i + m - 1] == p[m]) ans.push_back(i)

===Время работы===Алгоритм работает за <tex>O(m \cdot (n - m))</tex>. В худшем случае <tex> m = </tex> <tex dpi ="150"> \fracdfrac{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>, поэтому этот алгоритм достаточно широко применяется на практике.

== Сравнение с другими алгоритмами =====Преимущества===\begin{itemsize}\item Если <tex>m</tex> достаточно мало, по сравнению с <tex>n</tex>, то тогда асимптотика получается * Требует <tex>O(N1)</tex>памяти. Поэтому этот * Приемлемое время работы на практике (см. выше). Благодаря этом алгоритм активно используется применяется, например, в браузерах и текстовых редакторах (при использовании <textt> \mathrm{Ctrl}+\mathrm{F}</textt>), потому что обычно паттерн, который нужно найти , очень короткий по сравнению с самим текстом.Также наивный алгоритм используется в стандартных библиотеках языков высокого уровня (C++, Java), потому что он не требует дополнительной памяти.* Простая и понятная реализация.=== Недостатки ===\item * Требует <tex>O(1m \cdot (n-m))</tex> памятиопераций, вследствие чего алгоритм работает медленно в случае, когда длина паттерна достаточно велика (см.\item Простая и понятная реализациявыше).\end{itemize}

== Литература Источники информации ==* ''Кормен Т, Томас Х., Лейзерсон Ч, Чарльз И., Ривест Р, Рональд Л., Штайн Клиффорд'' ''' Алгоритмы: построение и анализ''', 3-е издание.[http://wmateПер.ru/ebooks/?dl=380&mirror=1] — 2-е издс англ. — М.: Издательский дом «Вильямс»"Вильямс", 20072014. — С1328 с.: ил. 1296— ISBN 978-5-8459-1794-2 (рус.) — страница 1034.