Изменения

{{Задача|definition ==Постановка задачи==Имеются строки Дан текст <tex>Tt[0 \,\mathinner{\ldotp\ldotp}\, n-1 .. n]</tex> и паттерн <tex>Pp[0 \,\mathinner{\ldotp\ldotp}\, m-1 .. m]</tex> такие, что <tex>n\geqslant m</tex> и элементы этих строк {{---}} символы из конечного алфавита <tex>\geSigma </tex> . Требуется проверить, входит ли паттерн <tex>mp</tex> и элементы этих строк <tex>-в текст </tex> символы из конечного алфавита <tex> \sum t</tex>. Говорят}}{{Определение|definition = Будем говорить, что строка паттерн <tex>Pp</tex> встречается в строке тексте <tex>Tt</tex> со сдвигом <tex>s</tex>, если <tex> 0 \le leqslant s \le leqslant n-m</tex> и <tex>Tt[s + 1 .. \,\mathinner{\ldotp\ldotp}\, s + m- 1] = P[1..m].p</tex> . Если строка <tex>Pp</tex> встречается в строке <tex>Tt</tex>, то <tex>Pp</tex> является подстрокой <tex>T</tex>. Требуется проверить, является ли строка <tex>P</tex> подстрокой <tex>Tt</tex>.}}

В наивном алгоритме поиск всех допустимых сдвигов производится с помощью цикла, в котором проверяется условие <tex>Tt[s + 1 .. \,\mathinner{\ldotp\ldotp}\, s + m- 1] = P[1..m] p</tex> для каждого из <tex> n - m + 1 </tex> возможных значений <tex>s</tex>.

===Псевдокод===Приведем пример псевдокода, который находит все вхождения строки <tex>Pp</tex> в <tex>Tt</tex> и возвращает массив позиций, откуда начинается начинаются вхождения. '''vector<int[]>''' naiveStringMatcher (Tt : '''string''', Pp : '''string'''): '''int''' n = t.length(T) '''int''' m = p.length(P) '''vector<int[] >''' ans;

'''if''' Tt[i..i + m - 1] == P[1..m]p ans.addpush_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>, поэтому этот алгоритм достаточно широко применяется на практике.

== Литература Сравнение с другими алгоритмами ===== Преимущества ===* Требует <tex>O(1)</tex> памяти.* Приемлемое время работы на практике (см. выше). Благодаря этом алгоритм применяется, например, в браузерах и текстовых редакторах (при использовании <tt>Ctrl + F</tt>), потому что обычно паттерн, который нужно найти, очень короткий по сравнению с самим текстом. Также наивный алгоритм используется в стандартных библиотеках языков высокого уровня (C++, Java), потому что он не требует дополнительной памяти.* Простая и понятная реализация.=== Недостатки ===* Требует <tex>O(m \cdot (n-m))</tex> операций, вследствие чего алгоритм работает медленно в случае, когда длина паттерна достаточно велика (см. выше). == Источники информации ==* ''Кормен Т, Томас Х., Лейзерсон Ч, Чарльз И., Ривест Р, Рональд Л., Штайн Клиффорд'' ''' Алгоритмы: построение и анализ''', 3-е издание.[http://wmateПер.ru/ebooks/?dl=380&mirror=1] — 2-е издс англ. — М.: Издательский дом «Вильямс»"Вильямс", 20072014. — С1328 с. 1296: ил. — ISBN 978-5-8459-1794-2 (рус.) — страница 1034.