Algoritmul de căutare text este o metodă fundamentală în procesarea textului și regăsirea informațiilor. Acest algoritm ne permite să localizăm și să identificăm aparițiile unui subșir(sau model) într-o bucată mai mare de text.
Cum functioneaza
- Începeți cu o bucată mai mare de text(sau document) și un subșir de căutat.
- Repetați fiecare caracter al textului succesiv.
- Comparați subșirul cu o porțiune a textului care are aceeași lungime ca și subșirul. Dacă se găsește o potrivire, înregistrați poziția curentă.
- Treceți la următoarea poziție și continuați comparația.
Exemplu
Luați în considerare textul: „Să căutăm un subșir în acest text pentru a vedea cum funcționează algoritmul”.
Și subșirul de căutat: „subșir”
- Începeți de la poziția 0. Comparați
Let'
cu „subșir”. Nu se potrivesc. - Treceți în poziția 1. Comparați
et's
cu „subșir”. Nu se potrivesc. - Mutați-vă în poziția 2. Comparați
t's
„ cu „subșir”. Nu se potrivește. - Treceți în poziția 3. Comparați
's s
cu „subșir”. Nu se potrivesc. - Treceți în poziția 4. Comparați
se
cu „subșir”. Nu se potrivesc. - Deplasați-vă în poziția 5. Comparați
sea
cu „subșir”. Nu se potrivesc. - Treceți în poziția 6. Comparați
earc
cu „subșir”. Nu se potrivesc. - Treceți în poziția 7. Comparați
arch
cu „subșir”. Nu se potrivesc. - Mutați-vă în poziția 8. Comparați
rch
„ cu „subșir”. Nu se potrivește. - Treceți în poziția 9. Comparați
ch w
cu „subșir”. Nu se potrivesc. - Mutați-vă în poziția 10. Comparați
h wi
cu „subșir”. Nu se potrivesc. - Mutați-vă în poziția 11. Comparați „
wit
cu „subșir”. Nu se potrivește. - Mutați-vă în poziția 12. Comparați
with
cu „subșir”. Nu se potrivesc. - Mutați-vă în poziția 13. Comparați
ithi
cu „subșir”. Nu se potrivesc. - Mutați-vă în poziția 14. Comparați
thin
cu „subșir”. Nu se potrivesc. - Mutați-vă în poziția 15. Comparați
hinn
cu „subșir”. Nu se potrivesc. - Mutați-vă în poziția 16. Comparați
in t
cu „subșir”. Nu se potrivesc. - Treceți la poziția 17. Comparați
n th
cu „subșir”. Nu se potrivesc. - Mutați-vă în poziția 18. Comparați „
thi
cu „subșir”. Nu se potrivește. - Mutați-vă în poziția 19. Comparați
this
cu „subșir”. Nu se potrivesc. - Mutați-vă în poziția 20. Comparați
his
„ cu „subșir”. Nu se potrivește. - Mutați-vă în poziția 21. Comparați
is t
cu „subșir”. Nu se potrivesc. - Mutați-vă în poziția 22. Comparați
s te
cu „subșir”. Nu se potrivesc. - Mutați-vă în poziția 23. Comparați
ubst
cu „subșir”. Nu se potrivesc. - Mutați-vă în poziția 24. Comparați
bstr
cu „subșir”. Nu se potrivesc. - Mutați-vă în poziția 25. Comparați
stre
cu „subșir”. Nu se potrivesc. - Mutați-vă în poziția 26. Comparați
trin
cu „subșir”. Nu se potrivesc. - Mutați-vă în poziția 27. Comparați
ring
cu „subșir”. Meci găsit, poziția record 27.
Subșirul „subșir” se găsește la poziția 27 în text.
Exemplu de cod în C++
În acest exemplu, textSearch
funcția este folosită pentru a găsi pozițiile subșirului „subșir” în text. Rezultatul va fi un vector care conține pozițiile de început ale meciurilor.