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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Тикет 2-1)
(Преимущества: удалил <tex> из не-формул)
Строка 26: Строка 26:
 
==Преимущества==
 
==Преимущества==
 
* Требует <tex>O(1)</tex> памяти.
 
* Требует <tex>O(1)</tex> памяти.
* Приемлемое время работы на практике (см. выше). Благодаря этом алгоритм применяется, например, в браузерах и текстовых редакторах (при использовании <tex> \mathrm{Ctrl} \texttt{+} \mathrm{F}</tex>), потому что обычно паттерн, который нужно найти очень короткий по сравнению с самим текстом. Также наивный алгоритм используется в стандартных библиотеках языков высокого уровня <tex>(\mathrm{C}\texttt{++},\ \mathrm{Java})</tex>, потому что он не требует дополнительной памяти.
+
* Приемлемое время работы на практике (см. выше). Благодаря этом алгоритм применяется, например, в браузерах и текстовых редакторах (при использовании <tt>Ctrl + F</tt>), потому что обычно паттерн, который нужно найти очень короткий по сравнению с самим текстом. Также наивный алгоритм используется в стандартных библиотеках языков высокого уровня (C++, Java), потому что он не требует дополнительной памяти.
 
* Простая и понятная реализация.
 
* Простая и понятная реализация.
  

Версия 21:17, 7 июня 2015

Задача:
Дан текст [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]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]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 to n - m + 1
      if t[i..i + m - 1] == p[1..m]
           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]O(1)[/math] памяти.
  • Приемлемое время работы на практике (см. выше). Благодаря этом алгоритм применяется, например, в браузерах и текстовых редакторах (при использовании Ctrl + F), потому что обычно паттерн, который нужно найти очень короткий по сравнению с самим текстом. Также наивный алгоритм используется в стандартных библиотеках языков высокого уровня (C++, Java), потому что он не требует дополнительной памяти.
  • Простая и понятная реализация.

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

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