130
правок
Изменения
→Сравнение алгоритмов: haystack, needle → text, pattern
== Сравнение алгоритмов ==
*<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(np^2)</tex>
|
|<tex>O(1)</tex>
|Single
|Прямой
|Сравнение — «чёрный ящик». Если <tex>np</tex> достаточно мало по сравнению с <tex>ht</tex>, то асимптотика будет близкой к <tex>O(ht)</tex>, что позволяет использовать его на практике в случаях, когда паттерн много меньше текста (например, ctrl+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
|Прямой
