Tekstihakualgoritmi on perusmenetelmä tekstinkäsittelyssä ja tiedonhaussa. Tämän algoritmin avulla voimme paikantaa ja tunnistaa alimerkkijonon(tai kuvion) esiintymät suuremmassa tekstissä.
Kuinka se toimii
- Aloita suuremmalla tekstinpalalla(tai asiakirjalla) ja haettavalla alimerkkijonolla.
- Toista tekstin jokainen merkki peräkkäin.
- Vertaa osamerkkijonoa tekstin osaan, jonka pituus on sama kuin alimerkkijono. Jos vastaavuus löytyy, tallenna nykyinen sijainti.
- Siirry seuraavaan kohtaan ja jatka vertailua.
Esimerkki
Harkitse tekstiä: "Etsitään tästä tekstistä alimerkkijonoa nähdäksemme, kuinka algoritmi toimii."
Ja etsittävä alimerkkijono: "alimerkkijono"
- Aloita paikasta 0. Vertaa
Let'
"alimerkkijonoon". Ei osumia. - Siirry kohtaan 1. Vertaa
et's
"alimerkkijonoon". Ei osumia. - Siirry kohtaan 2. Vertaa
t's
" ja "alimerkkijono". Ei vastaavuutta. - Siirry kohtaan 3. Vertaa
's s
"alimerkkijonoon". Ei osumia. - Siirry kohtaan 4. Vertaa
se
"alimerkkijonoon". Ei osumia. - Siirry kohtaan 5. Vertaa
sea
"alimerkkijonoon". Ei osumia. - Siirry kohtaan 6. Vertaa
earc
"alimerkkijonoon". Ei osumia. - Siirry kohtaan 7. Vertaa
arch
"alimerkkijonoon". Ei osumia. - Siirry kohtaan 8. Vertaa
rch
" ja "alimerkkijono". Ei vastaavuutta. - Siirry kohtaan 9. Vertaa
ch w
"alimerkkijonoon". Ei osumia. - Siirry kohtaan 10. Vertaa
h wi
"alimerkkijonoon". Ei osumia. - Siirry kohtaan 11. Vertaa "
wit
ja "alimerkkijono". Ei vastaavuutta. - Siirry kohtaan 12. Vertaa
with
"alimerkkijonoon". Ei osumia. - Siirry kohtaan 13. Vertaa
ithi
"alimerkkijonoon". Ei osumia. - Siirry kohtaan 14. Vertaa
thin
"alimerkkijonoon". Ei osumia. - Siirry kohtaan 15. Vertaa
hinn
"alimerkkijonoon". Ei osumia. - Siirry kohtaan 16. Vertaa
in t
"alimerkkijonoon". Ei osumia. - Siirry kohtaan 17. Vertaa
n th
"alimerkkijonoon". Ei osumia. - Siirry kohtaan 18. Vertaa "
thi
ja "alimerkkijono". Ei vastaavuutta. - Siirry kohtaan 19. Vertaa
this
"alimerkkijonoon". Ei osumia. - Siirry kohtaan 20. Vertaa
his
" ja "alimerkkijono". Ei vastaavuutta. - Siirry kohtaan 21. Vertaa
is t
"alimerkkijonoon". Ei osumia. - Siirry kohtaan 22. Vertaa
s te
"alimerkkijonoon". Ei osumia. - Siirry kohtaan 23. Vertaa
ubst
"alimerkkijonoon". Ei osumia. - Siirry kohtaan 24. Vertaa
bstr
"alimerkkijonoon". Ei osumia. - Siirry kohtaan 25. Vertaa
stre
"alimerkkijonoon". Ei osumia. - Siirry kohtaan 26. Vertaa
trin
"alimerkkijonoon". Ei osumia. - Siirry kohtaan 27. Vertaa
ring
"alimerkkijonoon". Ottelu löydetty, ennätyssijainti 27.
Osamerkkijono "alimerkkijono" löytyy tekstin kohdasta 27.
Esimerkkikoodi C++:ssa
Tässä esimerkissä funktiota textSearch
käytetään etsimään alimerkkijonon "alimerkkijono" paikat tekstistä. Tuloksena on vektori, joka sisältää otteluiden aloituspaikat.