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

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Задача:

Дан текст [math]t[0 \,\mathinner{\ldotp\ldotp}\, n-1][/math] и паттерн [math]p[0 \,\mathinner{\ldotp\ldotp}\, m-1][/math] такие, что [math]n \geqslant m[/math] и элементы этих строк — символы из конечного алфавита [math] \Sigma [/math]. Требуется проверить, входит ли паттерн [math]p[/math] в текст [math]t[/math].

Определение:

Будем говорить, что паттерн [math]p[/math] встречается в тексте [math]t[/math] со сдвигом [math]s[/math], если [math] 0 \leqslant s \leqslant n-m[/math] и [math]t[s \,\mathinner{\ldotp\ldotp}\, s + m - 1] = p[/math]. Если строка [math]p[/math] встречается в строке [math]t[/math], то [math]p[/math] является подстрокой [math]t[/math].

Алгоритм

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

Псевдокод

Приведем пример псевдокода, который находит все вхождения строки [math]p[/math] в [math]t[/math] и возвращает массив позиций, откуда начинаются вхождения.

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

Время работы

Алгоритм работает за [math]O(m \cdot (n - m))[/math]. В худшем случае [math] m = [/math] [math]\dfrac{n}{2}[/math], что даёт [math] O\left(\dfrac{n^2}{4}\right) = O\left(n^2\right) [/math]. Однако если [math]m[/math] достаточно мало по сравнению с [math]n[/math], то тогда асимптотика получается близкой к [math]O(n)[/math], поэтому этот алгоритм достаточно широко применяется на практике.

Сравнение с другими алгоритмами

Преимущества

• Требует [math]O(1)[/math] памяти.
• Приемлемое время работы на практике (см. выше). Благодаря этом алгоритм применяется, например, в браузерах и текстовых редакторах (при использовании Ctrl + F), потому что обычно паттерн, который нужно найти, очень короткий по сравнению с самим текстом. Также наивный алгоритм используется в стандартных библиотеках языков высокого уровня (C++, Java), потому что он не требует дополнительной памяти.
• Простая и понятная реализация.

Недостатки

• Требует [math]O(m \cdot (n-m))[/math] операций, вследствие чего алгоритм работает медленно в случае, когда длина паттерна достаточно велика (см. выше).

Источники информации

• Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 3-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2014. — 1328 с.: ил. — ISBN 978-5-8459-1794-2 (рус.) — страница 1034.