Наивный алгоритм поиска подстроки в строке

Постановка задачи

Имеются строки [math]T[1 .. n][/math] и [math]P[1 .. m][/math] такие, что [math]n[/math] [math]\ge[/math] [math]m[/math] и элементы этих строк [math]-[/math] символы из конечного алфавита [math] \sum [/math]. Говорят, что строка [math]P[/math] встречается в строке [math]T[/math] со сдвигом [math]s[/math], если [math] 0 \le s \le n-m[/math] и [math]T[s + 1 .. s + m][/math] = [math]P[1..m][/math]. Если строка [math]P[/math] встречается в строке [math]T[/math], то [math]P[/math] является подстрокой [math]T[/math]. Требуется проверить, является ли строка [math]P[/math] подстрокой [math]T[/math].

Алгоритм

В наивном алгоритме поиск всех допустимых сдвигов производится с помощью цикла, в котором проверяется условие [math]T[s + 1 .. s + m][/math] = [math]P[1..m][/math] для каждого из [math] n-m+1[/math] возможных значений [math]s[/math].

Псевдокод

naiveStringMatcher (T, P)
n = length(T)
m = length(P)
for s = 0 to n - m
     if T[s + 1 .. s + m] = P[1..m]
          print()

Время работы

Алгоритм работает за [math]O(m * (n - m))[/math]. В худшем случае [math] m = n / 2 [/math], что дает [math] O(n^2/4) = O(n^2) [/math].

Литература

• Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.[1] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.