Teksto paieškos algoritmas yra pagrindinis teksto apdorojimo ir informacijos gavimo metodas. Šis algoritmas leidžia mums rasti ir nustatyti poeilutės(arba šablono) atvejus didesnėje teksto dalyje.
Kaip tai veikia
- Pradėkite nuo didesnės teksto dalies(arba dokumento) ir ieškomos poeilutės.
- Pakartokite kiekvieną teksto simbolį iš eilės.
- Palyginkite eilutę su teksto dalimi, kurios ilgis yra toks pat, kaip ir poeilutė. Jei randama atitiktis, užrašykite dabartinę padėtį.
- Pereikite į kitą poziciją ir tęskite palyginimą.
Pavyzdys
Apsvarstykite tekstą: „Ieškokime poeilutės šiame tekste, kad pamatytume, kaip veikia algoritmas“.
Ir poeilutė, kurios reikia ieškoti: "substring"
- Pradėkite nuo 0 pozicijos. Palyginkite
Let'
su "substyle". Jokio atitikmens. - Perkelkite į 1 padėtį. Palyginkite
et's
su „substyle“. Jokio atitikmens. - Perkelkite į 2 padėtį. Palyginkite
t's
" su "substyling". Nėra atitikties. - Perkelkite į 3 padėtį. Palyginkite
's s
su „substyle“. Jokio atitikmens. - Perkelkite į 4 poziciją. Palyginkite
se
su "substyle". Jokio atitikmens. - Perkelkite į 5 padėtį. Palyginkite
sea
su "substyle". Jokio atitikmens. - Perkelkite į 6 poziciją. Palyginkite
earc
su „substyle“. Jokio atitikmens. - Perkelkite į 7 poziciją. Palyginkite
arch
su "substyle". Jokio atitikmens. - Perkelkite į 8 poziciją. Palyginkite
rch
" su "substyling". Atitikties nėra. - Perkelkite į 9 poziciją. Palyginkite
ch w
su "substyle". Jokio atitikmens. - Perkelkite į 10 padėtį. Palyginkite
h wi
su „substyle“. Jokio atitikmens. - Perkelkite į 11 poziciją. Palyginkite "
wit
su "substyling". Atitikties nėra. - Perkelkite į 12 poziciją. Palyginkite
with
su "substyle". Jokio atitikmens. - Perkelkite į 13 padėtį. Palyginkite
ithi
su "substyle". Jokio atitikmens. - Perkelkite į 14 poziciją. Palyginkite
thin
su "substyle". Jokio atitikmens. - Perkelkite į 15 poziciją. Palyginkite
hinn
su "substyle". Jokio atitikmens. - Perkelkite į 16 poziciją. Palyginkite
in t
su "substyle". Jokio atitikmens. - Perkelkite į 17 poziciją. Palyginkite
n th
su "substyle". Jokio atitikmens. - Perkelkite į 18 poziciją. Palyginkite "
thi
su "substyling". Atitikties nėra. - Perkelkite į 19 poziciją. Palyginkite
this
su "substyle". Jokio atitikmens. - Perkelkite į 20 poziciją. Palyginkite
his
" su "substyling". Nėra atitikties. - Perkelkite į 21 poziciją. Palyginkite
is t
su "substyle". Jokio atitikmens. - Perkelkite į 22 poziciją. Palyginkite
s te
su "substyle". Jokio atitikmens. - Perkelkite į 23 poziciją. Palyginkite
ubst
su "substyle". Jokio atitikmens. - Perkelkite į 24 poziciją. Palyginkite
bstr
su "substyle". Jokio atitikmens. - Perkelkite į 25 poziciją. Palyginkite
stre
su "substyle". Jokio atitikmens. - Perkelkite į 26 poziciją. Palyginkite
trin
su "substyle". Jokio atitikmens. - Perkelkite į 27 poziciją. Palyginkite
ring
su "substyle". Rungtynės rastas, rekordinė 27 vieta.
Poeilutė „poeilutė“ yra 27 teksto pozicijoje.
Kodo pavyzdys C++
Šiame pavyzdyje textSearch
funkcija naudojama norint rasti poeilutės „substyling“ vietas tekste. Rezultatas bus vektorius, kuriame yra rungtynių pradinės pozicijos.