Изменения
→Сравнение алгоритмов
'''Поиск подстроки в строке''' (англ. ''String searching algorithm'') — класс алгоритмов над строками, которые позволяют найти паттерн (''needlepattern'') в тексте (''haystacktext'').
== Классификация алгоритмов поиска подстроки в строке ==
Во всех алгоритмах этого типа сравнение является «чёрным ящиком» для программиста.
=== По порядку сравнения паттерна в тексте ===
==== Прямой ====
Преимущества:
* отсутствие регрессии на «плохих» данных.
==== Обратный ====
Паттерн движется по тексту слева на правонаправо, но сравнение подстрок происходит справа на левоналево. Преимущества: <tex>+</tex> При * при несовпадении позволяет перемещать паттерн по строке сразу на несколько символов. Недостатки:* производительность сильно зависит от данных.
==== Сравнение в необычном порядке ====
Сколько поисковых шаблонов может обработать алгоритм за один раз.
=== По необходимости препроцессинга текста ===
== Сравнение алгоритмов ==
*<tex>|\Sigma| = \sigma</tex> — размер алфавита
*<tex>|haystacktext| = ht</tex> — длина текста*<tex>|needlepattern| = np</tex> — длина паттерна
*<tex>a</tex> — размер ответа(кол-во пар)
*<tex>m</tex> — суммарная длина всех паттернов
|- align = "center"
|[[Наивный алгоритм поиска подстроки в строке| Наивный алгоритм <br>(Brute Force algorithm)]]
|<tex>O(n p \cdot (h t - np))</tex>|<tex>O(nt^2)</tex>
|
|<tex>O(1)</tex>
|Single
|Прямой
|Сравнение — «чёрный ящик». Если <tex>np</tex> достаточно мало по сравнению с <tex>ht</tex>, то асимптотика будет близкой к <tex>O(ht)</tex>, что позволяет использовать его на практике в случаях, когда паттерн много меньше текста (например, ctrlCtrl+F в браузерах)
|-align = "center"
|[[Z-функция| Поиск подстроки в строке с помощью Z-функции]]
|<tex>O(ht)</tex>|<tex>O(ht)</tex>|<tex>O(h p + nt)</tex>|<tex>O(np)</tex>
|Single
|Прямой
|- align = "center"
|[[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа| Алгоритм Рабина-Карпа <br>(Karp-Rabin algorithm)]]
|<tex>O(n p + ht)</tex>|<tex>O(nhpt)</tex>|<tex>O(np)</tex>
|<tex>O(1)</tex>
|Single / Finite
|- align = "center"
|[[Алгоритм Кнута-Морриса-Пратта| Алгоритм Кнута-Морриса-Пратта <br>(Knuth-Morris-Pratt algorith)]]
|<tex>O(n p + ht)</tex>|<tex>O(n p + ht)</tex>|<tex>O(np)</tex>|<tex>O(np)</tex>
|Single
|Прямой
|-align = "center"
|[[Алгоритм Колусси| Алгоритм Колусси <br>(Colussi algorithm)]]
|<tex>O(ht)</tex>|<tex>O(ht)</tex>|<tex>O(np)</tex>|<tex>O(np)</tex>
|Single
|Прямой / Обратный
|- align = "center"
|[[Алгоритм Ахо-Корасик| Алгоритм Ахо-Корасик <br>(Aho–Corasick string matching algorithm)]]
|<tex>O(m + h t + a)</tex>|<tex>O(ht)</tex>
|<br> <tex>O(m)</tex>
|<tex>O(m\sigma)</tex>
|-align = "center"
|[[Алгоритм Shift-Or]]
|<tex>O(ht)</tex>|<tex>O(h t \cdot \dfrac{n}{w})</tex> <br> <tex>w</tex> — размер машинного слова|<tex>O(n p + \sigma)</tex>|<tex>O(n p + \sigma)</tex>
|Single
|Прямой
|Использует тот факт, что в современных процессорах битовые сдвиг и или являются атомарными. Эффективен, если <tex>n p \leqslant w</tex>. Иначе деградирует и по памяти, и по сложности
|-align = "center"
|[[Алгоритм Бойера-Мура| Алгоритм Бойера-Мура <br>(Boyer-Moore algorithm)]]
|<tex>O(ht)</tex>|<tex>O(hnpt)</tex>|<tex>O(n p + \sigma)</tex>|<tex>O(n p + \sigma)</tex>
|Single
|Обратный
|-align = "center"
|[[Алгоритм поиска подстроки в строке с помощью суффиксного массива| Поиск подстроки в строке с помощью суффиксного массива <br>(Suffix array)]]
|<tex>O(np\log ht)</tex>|<tex>O(np\log ht)</tex>|<tex>O(ht)</tex>|<tex>O(ht)</tex>
|Single
|Прямой
|Использует [[Суффиксный массив]]. Если использовать [[Алгоритм Касаи и др.| Largest common prefix (lcp)]], то можно уменьшить асимптотику до <tex>O(n p + \log ht)</tex>. Суффиксный массив можно строить[[Построение суффиксного массива с помощью стандартных методов сортировки| стандартными способами]] или [[Алгоритм КаркайненаКарккайнена-Сандерса| алгоритмом КаркайненаКарккайнена-Сандерса]]. Асимптотика приведена для построения суффиксного массива с помощью алгоритма КаркайненаКарккайнена-Сандерса
|-align = "center"
|[[Сжатое суффиксное дерево| Поиск подстроки в строке с помощью суффиксного дерева <br>(Suffix tree)]]
|<tex>O(np)</tex>|<tex>O(np)</tex>|<tex>O(ht)</tex>|<tex>O(ht)</tex>
|Single
|Прямой
|Позволяет выполнять поиск подстроки в строке за линейное время
|- align = "center"
|[[Алгоритм Апостолико-Крочемора| Алгоритм Апостолико-Крочемора <br>( Apostolico-Crochemore algorithm)]]
|<tex>O(t)</tex>
|<tex>O(t)</tex>
|<tex>O(p)</tex>
|<tex>O(p)</tex>
|Single
|Прямой
|В худшем случае выполнит <tex>\dfrac{3}{2} n</tex> сравнений.
|}
