Tekstsøk-algoritmen er en grunnleggende metode i tekstbehandling og informasjonsinnhenting. Denne algoritmen lar oss lokalisere og identifisere forekomster av en delstreng(eller mønster) i et større stykke tekst.
Hvordan det fungerer
- Start med et større stykke tekst(eller dokument) og en delstreng å søke etter.
- Iterér gjennom hvert tegn i teksten sekvensielt.
- Sammenlign delstrengen med en del av teksten som har samme lengde som delstrengen. Hvis en match blir funnet, registrer gjeldende posisjon.
- Gå til neste posisjon og fortsett sammenligningen.
Eksempel
Tenk på teksten: "La oss søke etter en delstreng i denne teksten for å se hvordan algoritmen fungerer."
Og understrengen å søke etter: "understreng"
- Start på posisjon 0. Sammenlign
Let'
med "delstreng". Ingen treff. - Flytt til posisjon 1. Sammenlign
et's
med "delstreng". Ingen treff. - Flytt til posisjon 2. Sammenlign
t's
" med "understreng". Ingen samsvar. - Flytt til posisjon 3. Sammenlign
's s
med "delstreng". Ingen treff. - Flytt til posisjon 4. Sammenlign
se
med "understreng". Ingen treff. - Flytt til posisjon 5. Sammenlign
sea
med "delstreng". Ingen treff. - Flytt til posisjon 6. Sammenlign
earc
med "understreng". Ingen treff. - Flytt til posisjon 7. Sammenlign
arch
med "understreng". Ingen treff. - Flytt til posisjon 8. Sammenlign
rch
" med "delstreng". Ingen samsvar. - Flytt til posisjon 9. Sammenlign
ch w
med "understreng". Ingen treff. - Flytt til posisjon 10. Sammenlign
h wi
med "understreng". Ingen treff. - Flytt til posisjon 11. Sammenlign "
wit
med "understreng". Ingen samsvar. - Flytt til posisjon 12. Sammenlign
with
med "understreng". Ingen treff. - Flytt til posisjon 13. Sammenlign
ithi
med "delstreng". Ingen treff. - Flytt til posisjon 14. Sammenlign
thin
med "understreng". Ingen treff. - Flytt til posisjon 15. Sammenlign
hinn
med "understreng". Ingen treff. - Flytt til posisjon 16. Sammenlign
in t
med "understreng". Ingen treff. - Flytt til posisjon 17. Sammenlign
n th
med "understreng". Ingen treff. - Flytt til posisjon 18. Sammenlign "
thi
med "understreng". Ingen samsvar. - Flytt til posisjon 19. Sammenlign
this
med "delstreng". Ingen treff. - Flytt til posisjon 20. Sammenlign
his
" med "delstreng". Ingen samsvar. - Flytt til posisjon 21. Sammenlign
is t
med "understreng". Ingen treff. - Flytt til posisjon 22. Sammenlign
s te
med "delstreng". Ingen treff. - Flytt til posisjon 23. Sammenlign
ubst
med "understreng". Ingen treff. - Flytt til posisjon 24. Sammenlign
bstr
med "delstreng". Ingen treff. - Flytt til posisjon 25. Sammenlign
stre
med "delstreng". Ingen treff. - Flytt til posisjon 26. Sammenlign
trin
med "delstreng". Ingen treff. - Flytt til posisjon 27. Sammenlign
ring
med "understreng". Kamp funnet, rekordposisjon 27.
Delstrengen "understreng" finnes i posisjon 27 i teksten.
Eksempelkode i C++
I dette eksemplet textSearch
brukes funksjonen til å finne posisjonene til understrengen "understreng" i teksten. Resultatet vil være en vektor som inneholder startposisjonene til kampene.