Наивный алгоритм поиска подстроки в строке — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Псевдокод)
(Постановка задачи)
Строка 1: Строка 1:
 
==Постановка задачи==
 
==Постановка задачи==
Имеются строки <tex>t[1 .. n]</tex> и <tex>p[1 .. m]</tex> такие, что <tex>n</tex> <tex>\ge</tex> <tex>m</tex> и элементы этих строк  {{---}} символы из конечного алфавита <tex> \Sigma </tex>. Говорят, что строка <tex>p</tex> встречается в строке <tex>t</tex> со сдвигом <tex>s</tex>, если <tex> 0 \leqslant s \leqslant n-m</tex> и <tex>t[s + 1 .. s + m] = p[1..m].</tex> Если строка <tex>p</tex> встречается в строке <tex>t</tex>, то <tex>p</tex> является подстрокой <tex>t</tex>. Требуется проверить, является ли строка <tex>p</tex> подстрокой <tex>t</tex>.
+
Имеются строки <tex>t[1 .. n]</tex> и <tex>p[1 .. m]</tex> такие, что <tex>n \geqslant m</tex> и элементы этих строк  {{---}} символы из конечного алфавита <tex> \Sigma </tex>. Говорят, что строка <tex>p</tex> встречается в строке <tex>t</tex> со сдвигом <tex>s</tex>, если <tex> 0 \leqslant s \leqslant n-m</tex> и <tex>t[s + 1 .. s + m] = p[1..m].</tex> Если строка <tex>p</tex> встречается в строке <tex>t</tex>, то <tex>p</tex> является подстрокой <tex>t</tex>. Требуется проверить, является ли строка <tex>p</tex> подстрокой <tex>t</tex>.
  
 
==Алгоритм==
 
==Алгоритм==

Версия 09:00, 6 мая 2014

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

Имеются строки [math]t[1 .. n][/math] и [math]p[1 .. m][/math] такие, что [math]n \geqslant m[/math] и элементы этих строк — символы из конечного алфавита [math] \Sigma [/math]. Говорят, что строка [math]p[/math] встречается в строке [math]t[/math] со сдвигом [math]s[/math], если [math] 0 \leqslant s \leqslant n-m[/math] и [math]t[s + 1 .. s + m] = 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] = p[1..m] [/math] для каждого из [math] n - m + 1 [/math] возможных значений [math]s[/math].

Псевдокод

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

vector<int> naiveStringMatcher(string t, string p)
   int n = t.length
   int m = p.length
   vector<int> ans
   for i = 1 .. n - m + 1:
      if t.substring(i..i + m - 1) == p
           ans.push_back(i)
   return ans

Время работы

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

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

  • Если [math]m[/math] достаточно мало, по сравнению с [math]n[/math], то тогда асимптотика получается [math]O(N)[/math]. Поэтому этот алгоритм активно используется в браузерах (при использовании [math] \mathrm{Ctrl}+\mathrm{F}[/math]), потому что обычно паттерн, который нужно найти очень короткий по сравнению с самим текстом. Также наивный алгоритм используется в стандартных библиотеках языков высокого уровня [math](C[/math][math]++[/math][math], Java)[/math]. Это обусловлено тем, что в основном поиск подстроки используют в биоинформатике, а там тексты занимают сотни гигабайт, и памяти [math]O(N)[/math] никто не даст, также строки которые ищут обычно короткие, поэтому алгоритм в этом случае очень оптимален.
  • Требует [math]O(1)[/math] памяти.
  • Простая и понятная реализация.

Литература

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