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

Приміти́вний алгори́тм по́шуку рядка́ (англ. 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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.