http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=178.178.14.89&*Викиконспекты - Вклад участника [ru]2026-05-26T14:46:57ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B0%D0%B8%D0%B2%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%BF%D0%BE%D0%B4%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B8_%D0%B2_%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B5&diff=24428Наивный алгоритм поиска подстроки в строке2012-06-08T15:55:41Z<p>178.178.14.89: /* Время работы */</p>
<hr />
<div>==Постановка задачи==<br />
Имеются строки <tex>T[1 .. n]</tex> и <tex>P[1 .. m]</tex> такие, что <tex>n</tex> <tex>\ge</tex> <tex>m</tex> и элементы этих строк <tex>-</tex> символы из конечного алфавита <tex> \sum </tex>. Говорят, что строка <tex>P</tex> встречается в строке <tex>T</tex> со сдвигом <tex>s</tex>, если <tex> 0 \le s \le n-m</tex> и <tex>T[s + 1 .. s + m]</tex> = <tex>P[1..m]</tex>. Если строка <tex>P</tex> встречается в строке <tex>T</tex>, то <tex>P</tex> является подстрокой <tex>T</tex>. Требуется проверить, является ли строка <tex>P</tex> подстрокой <tex>T</tex>.<br />
<br />
==Алгоритм==<br />
В наивном алгоритме поиск всех допустимых сдвигов производится с помощью цикла, в котором проверяется условие <tex>T[s + 1 .. s + m]</tex> = <tex>P[1..m]</tex> для каждого из <tex> n-m+1</tex> возможных значений <tex>s</tex>.<br />
<br />
==Псевдокод==<br />
<br />
'''naiveStringMatcher''' (T, P)<br />
n = length(T)<br />
m = length(P)<br />
'''for''' s = 0 '''to''' n - m<br />
'''if''' T[s + 1 .. s + m] = P[1..m]<br />
print()<br />
<br />
==Время работы==<br />
Алгоритм работает за <tex>O(m \cdot (n - m))</tex>. В худшем случае <tex> m = n / 2 </tex>, что дает <tex> O(n^2/4) = O(n^2) </tex>.<br />
<br />
== Литература ==<br />
* ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ.[http://wmate.ru/ebooks/?dl=380&mirror=1] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.</div>178.178.14.89