Примітивний алгоритм пошуку рядка

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

Алгоритм не є ефективним, але він не потребує додаткової пам'яті і тому входить до стандартних бібліотек більшості мов програмування.

Ідея алгоритму

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

Псевдокод

$\;Naive\_String\_Matcher(T,P)$
1 $n\leftarrow length[T]$
2 $m\leftarrow length[P]$
3 for $s\leftarrow 0$ to $\;n-m$
4     do if $\;P[1..m]=T[s+1..s+m]$
5           then print "Зразок знайдено зі здвигом" $\;s$

Оцінка складності роботи

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

Тут n — довжина тексту, m — довжина зразка.

Джерела

• Thimas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (2nd ed.) The MIT Press. ISBN 0-07-013151-1.