Tekstsøgningsalgoritmen er en grundlæggende metode til tekstbehandling og informationssøgning. Denne algoritme giver os mulighed for at lokalisere og identificere forekomster af en understreng(eller et mønster) i et større stykke tekst.
Hvordan det virker
- Start med et større stykke tekst(eller dokument) og en understreng at søge efter.
- Gentag gennem hvert tegn i teksten sekventielt.
- Sammenlign understrengen med en del af teksten, der har samme længde som understrengen. Hvis der findes et match, skal du registrere den aktuelle position.
- Flyt til næste position og fortsæt sammenligningen.
Eksempel
Overvej teksten: "Lad os søge efter en understreng i denne tekst for at se, hvordan algoritmen fungerer."
Og understrengen, der skal søges efter: "understreng"
- Start ved position 0. Sammenlign
Let'
med "understreng". Intet match. - Flyt til position 1. Sammenlign
et's
med "understreng". Intet match. - Flyt til position 2. Sammenlign
t's
" med "understreng". Ingen match. - Flyt til position 3. Sammenlign
's s
med "understreng". Intet match. - Flyt til position 4. Sammenlign
se
med "understreng". Intet match. - Flyt til position 5. Sammenlign
sea
med "understreng". Intet match. - Flyt til position 6. Sammenlign
earc
med "understreng". Intet match. - Flyt til position 7. Sammenlign
arch
med "understreng". Intet match. - Flyt til position 8. Sammenlign
rch
" med "understreng". Ingen match. - Flyt til position 9. Sammenlign
ch w
med "understreng". Intet match. - Flyt til position 10. Sammenlign
h wi
med "understreng". Intet match. - Flyt til position 11. Sammenlign "
wit
med "understreng". Ingen match. - Flyt til position 12. Sammenlign
with
med "understreng". Intet match. - Flyt til position 13. Sammenlign
ithi
med "understreng". Intet match. - Flyt til position 14. Sammenlign
thin
med "understreng". Intet match. - Flyt til position 15. Sammenlign
hinn
med "understreng". Intet match. - Flyt til position 16. Sammenlign
in t
med "understreng". Intet match. - Flyt til position 17. Sammenlign
n th
med "understreng". Intet match. - Flyt til position 18. Sammenlign "
thi
med "understreng". Ingen match. - Flyt til position 19. Sammenlign
this
med "understreng". Intet match. - Flyt til position 20. Sammenlign
his
" med "understreng". Ingen match. - Flyt til position 21. Sammenlign
is t
med "understreng". Intet match. - Flyt til position 22. Sammenlign
s te
med "understreng". Intet match. - Flyt til position 23. Sammenlign
ubst
med "understreng". Intet match. - Flyt til position 24. Sammenlign
bstr
med "understreng". Intet match. - Flyt til position 25. Sammenlign
stre
med "understreng". Intet match. - Flyt til position 26. Sammenlign
trin
med "understreng". Intet match. - Flyt til position 27. Sammenlign
ring
med "understreng". Match fundet, rekordposition 27.
Understrengen "understreng" findes på position 27 i teksten.
Eksempelkode i C++
I dette eksempel textSearch
bruges funktionen til at finde positionerne af understrengen "understreng" i teksten. Resultatet vil være en vektor, der indeholder startpositionerne for kampene.