Algoritam pretraživanja teksta temeljna je metoda u obradi teksta i pronalaženju informacija. Ovaj nam algoritam omogućuje lociranje i prepoznavanje pojavljivanja podniza(ili uzorka) unutar većeg dijela teksta.
Kako radi
- Započnite s većim dijelom teksta(ili dokumenta) i podniskom za traženje.
- Redom iterirajte kroz svaki znak teksta.
- Usporedite podniz s dijelom teksta koji ima istu duljinu kao podniz. Ako se pronađe podudaranje, zabilježite trenutni položaj.
- Prijeđite na sljedeću poziciju i nastavite usporedbu.
Primjer
Razmotrite tekst: "Potražimo podniz unutar ovog teksta da vidimo kako algoritam radi."
I podniz za traženje: "podniz"
- Započnite na poziciji 0. Usporedite
Let'
s "podniskom". Nema podudaranja. - Pomakni se na poziciju 1. Usporedi
et's
s "podniskom". Nema podudaranja. - Pomakni se na poziciju 2. Usporedi
t's
" s "podniskom". Nema podudaranja. - Pomakni se na poziciju 3. Usporedi
's s
s "podniskom". Nema podudaranja. - Pomakni se na poziciju 4. Usporedi
se
s "podniskom". Nema podudaranja. - Pomaknite se na poziciju 5. Usporedite
sea
s "podniskom". Nema podudaranja. - Pomaknite se na poziciju 6. Usporedite
earc
s "podniskom". Nema podudaranja. - Pomaknite se na poziciju 7. Usporedite
arch
s "podniskom". Nema podudaranja. - Pomakni se na poziciju 8. Usporedi
rch
" s "podniskom". Nema podudaranja. - Pomaknite se na poziciju 9. Usporedite
ch w
s "podniskom". Nema podudaranja. - Pomaknite se na poziciju 10. Usporedite
h wi
s "podniskom". Nema podudaranja. - Pomakni se na poziciju 11. Usporedi "
wit
s "podniskom". Nema podudaranja. - Pomaknite se na poziciju 12. Usporedite
with
s "podniskom". Nema podudaranja. - Pomaknite se na poziciju 13. Usporedite
ithi
s "podniskom". Nema podudaranja. - Pomaknite se na poziciju 14. Usporedite
thin
s "podniskom". Nema podudaranja. - Pomaknite se na poziciju 15. Usporedite
hinn
s "podniskom". Nema podudaranja. - Pomaknite se na poziciju 16. Usporedite
in t
s "podniskom". Nema podudaranja. - Pomaknite se na poziciju 17. Usporedite
n th
s "podniskom". Nema podudaranja. - Pomakni se na poziciju 18. Usporedi "
thi
s "podniskom". Nema podudaranja. - Pomaknite se na poziciju 19. Usporedite
this
s "podniskom". Nema podudaranja. - Pomakni se na poziciju 20. Usporedi
his
" s "podniskom". Nema podudaranja. - Pomaknite se na poziciju 21. Usporedite
is t
s "podniskom". Nema podudaranja. - Pomaknite se na poziciju 22. Usporedite
s te
s "podniskom". Nema podudaranja. - Pomaknite se na poziciju 23. Usporedite
ubst
s "podniskom". Nema podudaranja. - Pomaknite se na poziciju 24. Usporedite
bstr
s "podniskom". Nema podudaranja. - Pomaknite se na poziciju 25. Usporedite
stre
s "podniskom". Nema podudaranja. - Pomaknite se na poziciju 26. Usporedite
trin
s "podniskom". Nema podudaranja. - Pomaknite se na poziciju 27. Usporedite
ring
s "podniskom". Podudaranje pronađeno, rekordna pozicija 27.
Podniz "substring" nalazi se na poziciji 27 unutar teksta.
Primjer koda u C++
U ovom primjeru, textSearch
funkcija se koristi za pronalaženje položaja podniza "substring" unutar teksta. Rezultat će biti vektor koji sadrži početne pozicije utakmica.