Примітивний алгоритм пошуку рядка
Приміти́вний алгори́тм по́шуку рядка́ (англ. 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 "Зразок знайдено зі здвигом"
![{\displaystyle n\leftarrow length[T]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9b28d90d2c504e9a5a4fce5916dd545942830c76)
![{\displaystyle m\leftarrow length[P]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d0bfd1b6da75b5d5279fd1b10ca79b19bbf109b)
![{\displaystyle \;P[1..m]=T[s+1..s+m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f605dc0d684ef03ed72022574cb9c1fea8301682)
Оцінка складності роботи ред.
Так як алгоритм перебирає 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.