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

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

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

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

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

Псевдокод


1 
2 
3 for  to 
4     do if 
5           then print "Зразок знайдено зі здвигом" 

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

Так як алгоритм перебирає 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.