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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Постановка задачи)
м (Источники информации: добавлена категория)
(не показано 27 промежуточных версий 4 участников)
Строка 1: Строка 1:
==Постановка задачи==
+
{{Задача
Имеются строки <tex>t[1 .. n]</tex> и <tex>p[1 .. m]</tex> такие, что <tex>n</tex> <tex>\ge</tex> <tex>m</tex> и элементы этих строк  <tex>-</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>.
+
|definition = Дан текст <tex>t[0 \,\mathinner{\ldotp\ldotp}\, n-1]</tex> и паттерн <tex>p[0 \,\mathinner{\ldotp\ldotp}\, m-1]</tex> такие, что <tex>n \geqslant m</tex> и элементы этих строк  {{---}} символы из конечного алфавита <tex> \Sigma </tex>. Требуется проверить, входит ли паттерн <tex>p</tex> в текст <tex>t</tex>.
 +
}}
 +
{{Определение
 +
|definition = Будем говорить, что паттерн <tex>p</tex> встречается в тексте <tex>t</tex> со сдвигом <tex>s</tex>, если <tex> 0 \leqslant s \leqslant n-m</tex> и <tex>t[s \,\mathinner{\ldotp\ldotp}\, s + m - 1] = p</tex>. Если строка <tex>p</tex> встречается в строке <tex>t</tex>, то <tex>p</tex> является подстрокой <tex>t</tex>.  
 +
}}
  
 
==Алгоритм==
 
==Алгоритм==
В наивном алгоритме поиск всех допустимых сдвигов производится с помощью цикла, в котором проверяется условие <tex>t[s + 1 .. s + m] = p[1..m] </tex> для каждого из <tex> n - m + 1 </tex>  возможных значений <tex>s</tex>.
+
В наивном алгоритме поиск всех допустимых сдвигов производится с помощью цикла, в котором проверяется условие
 +
<tex>t[s \,\mathinner{\ldotp\ldotp}\, s + m - 1] = p</tex> для каждого из <tex> n - m + 1 </tex>  возможных значений <tex>s</tex>.
  
==Псевдокод==
+
===Псевдокод===
 
Приведем пример псевдокода, который находит все вхождения строки <tex>p</tex> в <tex>t</tex> и возвращает массив позиций, откуда начинаются вхождения.
 
Приведем пример псевдокода, который находит все вхождения строки <tex>p</tex> в <tex>t</tex> и возвращает массив позиций, откуда начинаются вхождения.
  '''vector<int>''' naiveStringMatcher ('''string''' t, '''string''' p)
+
  '''vector<int>''' naiveStringMatcher(t : '''string''', p : '''string'''):
 
     '''int''' n = t.length
 
     '''int''' n = t.length
 
     '''int''' m = p.length
 
     '''int''' m = p.length
 
     '''vector<int>''' ans
 
     '''vector<int>''' ans
     '''for''' i = 1 .. n - m + 1
+
     '''for''' i = 0 '''to''' n - m
       '''if''' (t[i] == p[1]) '''and''' (t[i + 1] == p[2]) .. '''and''' (t[i + m - 1] == p[m])
+
       '''if''' t[i .. i + m - 1] == p
            ans.push_back(i)
+
          ans.push_back(i)
 
     '''return''' ans
 
     '''return''' ans
  
==Время работы==
+
===Время работы===
Алгоритм работает за <tex>O(m \cdot (n - m))</tex>. В худшем случае <tex> m = </tex> <tex dpi ="150"> \frac{n}{2}, </tex> что дает <tex> O(n^2/4) = O(n^2) </tex>.
+
Алгоритм работает за <tex>O(m \cdot (n - m))</tex>. В худшем случае <tex> m = </tex> <tex>\dfrac{n}{2}</tex>, что даёт <tex> O\left(\dfrac{n^2}{4}\right) = O\left(n^2\right) </tex>.
 +
Однако если <tex>m</tex> достаточно мало по сравнению с <tex>n</tex>, то тогда асимптотика получается близкой к <tex>O(n)</tex>, поэтому этот алгоритм достаточно широко применяется на практике.
  
==Преимущества==
+
== Сравнение с другими алгоритмами ==
<tex>1) </tex> Если <tex>m</tex> достаточно мало, по сравнению с <tex>n</tex>, то тогда асимптотика получается <tex>O(N)</tex>. Поэтому этот алгоритм активно используется в браузерах (при использовании <tex>Ctrl+F</tex>), потому что обычно паттерн, который нужно найти очень короткий по сравнению с самим текстом.
+
=== Преимущества ===
 +
* Требует <tex>O(1)</tex> памяти.
 +
* Приемлемое время работы на практике (см. выше). Благодаря этом алгоритм применяется, например, в браузерах и текстовых редакторах (при использовании <tt>Ctrl + F</tt>), потому что обычно паттерн, который нужно найти, очень короткий по сравнению с самим текстом. Также наивный алгоритм используется в стандартных библиотеках языков высокого уровня (C++, Java), потому что он не требует дополнительной памяти.
 +
* Простая и понятная реализация.
 +
=== Недостатки ===
 +
* Требует <tex>O(m \cdot (n-m))</tex> операций, вследствие чего алгоритм работает медленно в случае, когда длина паттерна достаточно велика (см. выше).
  
<tex>2) </tex> Требует <tex>O(1)</tex> памяти.
+
== Источники информации ==
 
+
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 3-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2014. — 1328 с.: ил. — ISBN 978-5-8459-1794-2 (рус.) — страница 1034.
<tex>3)</tex> Простая и понятная реализация.
 
 
 
== Литература ==
 
* ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ.[http://wmate.ru/ebooks/?dl=380&mirror=1] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.
 
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Поиск подстроки в строке]]
 
[[Категория:Поиск подстроки в строке]]
 +
[[Категория:Точный поиск]]

Версия 14:48, 2 февраля 2016

Задача:
Дан текст [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.