Изменения

|definition = Дан текст <tex>t[1 {} .. 0 \,\mathinner{\ldotp\ldotp} \, n-1]</tex> и паттерн <tex>p[0 \,\mathinner{\ldotp\ldotp}\, m-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 .. \,\mathinner{\ldotp\ldotp}\, s + m- 1] = p[1..m].</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..i + m - 1] == p[1..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>, поэтому этот алгоритм достаточно широко применяется на практике.

* Приемлемое время работы на практике (см. выше). Благодаря этом алгоритм применяется, например, в браузерах и текстовых редакторах (при использовании <tt>Ctrl + F</tt>), потому что обычно паттерн, который нужно найти , очень короткий по сравнению с самим текстом. Также наивный алгоритм используется в стандартных библиотеках языков высокого уровня (C++, Java), потому что он не требует дополнительной памяти.