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

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

Имеются строки [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].

Псевдокод

Naive_String_Matcher ([math]T,P[/math])
[math]n \leftarrow length[T][/math]
[math]m \leftarrow length[P][/math]
for [math]s \leftarrow 0[/math] to [math]n - m[/math]
     if [math]T[s + 1 .. s + m][/math] = [math]P[1..m][/math]
          then 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.