Изменения

Перейти к: навигация, поиск

Наивный алгоритм поиска подстроки в строке

444 байта добавлено, 19:56, 5 мая 2014
Преимущества
==Преимущества==
*Если <tex>m</tex> достаточно мало, по сравнению с <tex>n</tex>, то тогда асимптотика получается <tex>O(N)</tex>. Поэтому этот алгоритм активно используется в браузерах (при использовании <tex> \mathrm{Ctrl}+\mathrm{F}</tex>), потому что обычно паттерн, который нужно найти очень короткий по сравнению с самим текстом. Также наивный алгоритм используется в стандартных библиотеках языков высокого уровня <tex>(C</tex><tex dpi = "100">++</tex><tex>, Java)</tex>. Это обусловлено тем, что в основном поиск подстроки используют в биоинформатике, а там тексты занимают сотни гигабайт, и памяти <tex>O(N)</tex> никто не даст, также строки которые ищут обычно короткие, поэтому алгоритм в этом случае очень оптимален.
*Требует <tex>O(1)</tex> памяти.
*Простая и понятная реализация.
668
правок

Навигация