1632
правки
Изменения
м
'''Naive_String_Matcher''' (===Время работы===Алгоритм работает за <tex>T,PO(m \cdot (n - m))</tex>) . В худшем случае <tex>n \leftarrow length[T]m = </tex> <tex>m \leftarrow length[P]dfrac{n}{2}</tex> '''for''' , что даёт <tex>s O\left(\leftarrow 0dfrac{n^2}{4}\right) = O\left(n^2\right) </tex> to .Однако если <tex>n - m</tex> '''do if''' достаточно мало по сравнению с <tex>T[s + 1 .. s + m]n</tex> = , то тогда асимптотика получается близкой к <tex>P[1..m]O(n)</tex> '''then''' print() , поэтому этот алгоритм достаточно широко применяется на практике.
rollbackEdits.php mass rollback
{{Задача|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]</tex> = <tex>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]</tex> = <tex>P[1..m]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(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. [[Категория:Алгоритмы и структуры данных]][[Категория:Поиск подстроки в строке]][[Категория:Точный поиск]]
