Algoritem iskanja po besedilu je temeljna metoda pri obdelavi besedila in iskanju informacij. Ta algoritem nam omogoča, da poiščemo in identificiramo pojavitve podniza(ali vzorca) znotraj večjega dela besedila.
Kako deluje
- Začnite z večjim delom besedila(ali dokumenta) in podnizom za iskanje.
- Zaporedoma preletite vsak znak besedila.
- Primerjajte podniz z delom besedila, ki ima enako dolžino kot podniz. Če se najde ujemanje, zabeležite trenutni položaj.
- Premaknite se na naslednji položaj in nadaljujte s primerjavo.
Primer
Razmislite o besedilu: "Poiščimo podniz v tem besedilu, da vidimo, kako deluje algoritem."
In podniz za iskanje: "substring"
- Začnite na položaju 0. Primerjajte
Let'
s "podnizom". Ni ujemanj. - Premakni se na položaj 1. Primerjaj
et's
s "podnizom". Ni ujemanj. - Premakni se na položaj 2. Primerjaj
t's
" s "podnizom". Ni ujemanja. - Premakni se na položaj 3. Primerjaj
's s
s "podnizom". Ni ujemanj. - Premakni se na položaj 4. Primerjaj
se
s "podnizom". Ni ujemanj. - Premakni se na položaj 5. Primerjaj
sea
s "podnizom". Ni ujemanj. - Premakni se na položaj 6. Primerjaj
earc
s "podnizom". Ni ujemanj. - Premakni se na položaj 7. Primerjaj
arch
s "podnizom". Ni ujemanj. - Premakni se na položaj 8. Primerjaj
rch
" s "podnizom". Ni ujemanja. - Premakni se na položaj 9. Primerjaj
ch w
s "podnizom". Ni ujemanj. - Premakni se na položaj 10. Primerjaj
h wi
s "podnizom". Ni ujemanj. - Premakni se na položaj 11. Primerjaj "
wit
s "podnizom". Ni ujemanja. - Premakni se na položaj 12. Primerjaj
with
s "podnizom". Ni ujemanj. - Premakni se na položaj 13. Primerjaj
ithi
s "podnizom". Ni ujemanj. - Premakni se na položaj 14. Primerjaj
thin
s "podnizom". Ni ujemanj. - Premakni se na položaj 15. Primerjaj
hinn
s "podnizom". Ni ujemanj. - Premakni se na položaj 16. Primerjaj
in t
s "podnizom". Ni ujemanj. - Premakni se na položaj 17. Primerjaj
n th
s "podnizom". Ni ujemanj. - Premakni se na položaj 18. Primerjaj "
thi
s "podnizom". Ni ujemanja. - Premakni se na položaj 19. Primerjaj
this
s "podnizom". Ni ujemanj. - Premakni se na položaj 20. Primerjaj
his
" s "podnizom". Ni ujemanja. - Premakni se na položaj 21. Primerjaj
is t
s "podnizom". Ni ujemanj. - Premakni se na položaj 22. Primerjaj
s te
s "podnizom". Ni ujemanj. - Premakni se na položaj 23. Primerjaj
ubst
s "podnizom". Ni ujemanj. - Premakni se na položaj 24. Primerjaj
bstr
s "podnizom". Ni ujemanj. - Premakni se na položaj 25. Primerjaj
stre
s "podnizom". Ni ujemanj. - Premakni se na položaj 26. Primerjaj
trin
s "podnizom". Ni ujemanj. - Premakni se na položaj 27. Primerjaj
ring
s "podnizom". Ujemanje najdeno, rekordno mesto 27.
Podniz "substring" se nahaja na mestu 27 znotraj besedila.
Primer kode v C++
V tem primeru textSearch
se funkcija uporablja za iskanje položajev podniza "substring" v besedilu. Rezultat bo vektor, ki vsebuje začetne položaje tekem.