Textsökningsalgoritmen är en grundläggande metod för textbearbetning och informationssökning. Denna algoritm tillåter oss att lokalisera och identifiera förekomster av en delsträng(eller mönster) i en större textbit.
Hur det fungerar
- Börja med en större bit text(eller dokument) och en delsträng att söka efter.
- Iterera genom varje tecken i texten sekventiellt.
- Jämför delsträngen med en del av texten som har samma längd som delsträngen. Om en matchning hittas, registrera den aktuella positionen.
- Flytta till nästa position och fortsätt jämförelsen.
Exempel
Tänk på texten: "Låt oss söka efter en delsträng i den här texten för att se hur algoritmen fungerar."
Och delsträngen att söka efter: "delsträng"
- Börja vid position 0. Jämför
Let'
med "delsträng". Ingen match. - Flytta till position 1. Jämför
et's
med "delsträng". Ingen match. - Flytta till position 2. Jämför
t's
" med "delsträng". Ingen matchning. - Flytta till position 3. Jämför
's s
med "delsträng". Ingen match. - Flytta till position 4. Jämför
se
med "delsträng". Ingen match. - Flytta till position 5. Jämför
sea
med "delsträng". Ingen match. - Flytta till position 6. Jämför
earc
med "delsträng". Ingen match. - Flytta till position 7. Jämför
arch
med "delsträng". Ingen match. - Flytta till position 8. Jämför
rch
" med "delsträng". Ingen matchning. - Flytta till position 9. Jämför
ch w
med "delsträng". Ingen match. - Flytta till position 10. Jämför
h wi
med "delsträng". Ingen match. - Flytta till position 11. Jämför "
wit
med "delsträng". Ingen matchning. - Flytta till position 12. Jämför
with
med "delsträng". Ingen match. - Flytta till position 13. Jämför
ithi
med "delsträng". Ingen match. - Flytta till position 14. Jämför
thin
med "delsträng". Ingen match. - Flytta till position 15. Jämför
hinn
med "delsträng". Ingen match. - Flytta till position 16. Jämför
in t
med "delsträng". Ingen match. - Flytta till position 17. Jämför
n th
med "delsträng". Ingen match. - Flytta till position 18. Jämför "
thi
med "delsträng". Ingen matchning. - Flytta till position 19. Jämför
this
med "delsträng". Ingen match. - Flytta till position 20. Jämför
his
" med "delsträng". Ingen matchning. - Flytta till position 21. Jämför
is t
med "delsträng". Ingen match. - Flytta till position 22. Jämför
s te
med "delsträng". Ingen match. - Flytta till position 23. Jämför
ubst
med "delsträng". Ingen match. - Flytta till position 24. Jämför
bstr
med "delsträng". Ingen match. - Flytta till position 25. Jämför
stre
med "delsträng". Ingen match. - Flytta till position 26. Jämför
trin
med "delsträng". Ingen match. - Flytta till position 27. Jämför
ring
med "delsträng". Match hittad, rekordposition 27.
Delsträngen "delsträng" finns vid position 27 i texten.
Exempelkod i C++
I det här exemplet textSearch
används funktionen för att hitta positionerna för delsträngen "delsträng" i texten. Resultatet blir en vektor som innehåller startpositionerna för matcherna.