Примитивный алгоритм поиска строки (англ. Naïve string search algorithm) — самый алгоритм, решает задачу нахождения расположения строки в тексте.

Алгоритм не является эффективным, но он не требует дополнительной памяти и поэтому входит в стандартных библиотек большинства языков программирования.

Идея алгоритма

Идея заключается в последовательной проверке всех возможных начальных оползней. Для каждого сдвига s проверяется равенство P [1..m] = T [s + 1..s + m].

Оценка сложности работы

Так как алгоритм перебирает n возможных оползней, и для каждого сдвига выполняется сравнение строк в m операций, то сложность всего поиска является Θ (nm).

Здесь n — длина текста, m — длина образца.