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

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

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

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

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

Псевдокод

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