A szövegkereső algoritmus a szövegfeldolgozás és információ-visszakeresés alapvető módszere. Ez az algoritmus lehetővé teszi számunkra, hogy megkeressük és azonosítsuk egy részkarakterlánc(vagy minta) előfordulásait egy nagyobb szövegrészen belül.
Hogyan működik
- Kezdje egy nagyobb szövegrészlettel(vagy dokumentummal) és a keresendő részkarakterlánccal.
- Iteráld végig a szöveg minden karakterét egymás után.
- Hasonlítsa össze az alkarakterláncot a szöveg egy részével, amelynek hossza megegyezik az alkarakterlánccal. Ha talál egyezést, rögzítse az aktuális pozíciót.
- Lépjen a következő pozícióra, és folytassa az összehasonlítást.
Példa
Fontolja meg a szöveget: "Keressünk egy részkarakterláncot ebben a szövegben, hogy lássuk, hogyan működik az algoritmus."
És a keresendő részkarakterlánc: "substring"
- Kezdje a 0. pozícióban. Hasonlítsa össze
Let'
az "alkarakterlánccal". Nem egyezik. - Lépjen az 1. pozícióba. Hasonlítsa össze
et's
az "alkarakterlánccal". Nem egyezik. - Lépjen a 2. pozícióba. Hasonlítsa össze
t's
a " karakterláncot " az "alkarakterlánccal". Nincs egyezés. - Lépjen a 3. pozícióba. Hasonlítsa össze
's s
az "alkarakterlánccal". Nem egyezik. - Lépjen a 4. pozícióba. Hasonlítsa össze
se
az "alkarakterlánccal". Nem egyezik. - Lépjen az 5. pozícióba. Hasonlítsa össze
sea
az "alkarakterlánccal". Nem egyezik. - Lépjen a 6. pozícióba. Hasonlítsa össze
earc
az "alkarakterlánccal". Nem egyezik. - Lépjen a 7. pozícióba. Hasonlítsa össze
arch
az "alkarakterlánccal". Nem egyezik. - Lépjen a 8. pozícióba. Hasonlítsa össze
rch
a " részt az "alkarakterlánccal". Nincs egyezés. - Lépjen a 9. pozícióba. Hasonlítsa össze
ch w
az "alkarakterlánccal". Nem egyezik. - Lépjen a 10. pozícióba. Hasonlítsa össze
h wi
az "alkarakterlánccal". Nem egyezik. - Lépjen a 11. pozícióba. Hasonlítsa össze a "
wit
részt az "alkarakterlánccal". Nincs egyezés. - Lépjen a 12. pozícióba. Hasonlítsa össze
with
az "alkarakterlánccal". Nem egyezik. - Lépjen a 13. pozícióba. Hasonlítsa össze
ithi
az "alkarakterlánccal". Nem egyezik. - Lépjen a 14. pozícióba. Hasonlítsa össze
thin
az "alkarakterlánccal". Nem egyezik. - Lépjen a 15. pozícióba. Hasonlítsa össze
hinn
az "alkarakterlánccal". Nem egyezik. - Lépjen a 16. pozícióba. Hasonlítsa össze
in t
az "alkarakterlánccal". Nem egyezik. - Lépjen a 17. pozícióba. Hasonlítsa össze
n th
az "alkarakterlánccal". Nem egyezik. - Lépjen a 18. pozícióba. Hasonlítsa össze a "
thi
részt az "alkarakterlánccal". Nincs egyezés. - Lépjen a 19. pozícióba. Hasonlítsa össze
this
az "alkarakterlánccal". Nem egyezik. - Lépjen a 20. pozícióba. Hasonlítsa össze
his
a " részt az "alkarakterlánccal". Nincs egyezés. - Lépjen a 21. pozícióba. Hasonlítsa össze
is t
az "alkarakterlánccal". Nem egyezik. - Lépjen a 22. pozícióba. Hasonlítsa össze
s te
az "alkarakterlánccal". Nem egyezik. - Lépjen a 23. pozícióba. Hasonlítsa össze
ubst
az "alkarakterlánccal". Nem egyezik. - Lépjen a 24. pozícióba. Hasonlítsa össze
bstr
az "alkarakterlánccal". Nem egyezik. - Lépjen a 25. pozícióba. Hasonlítsa össze
stre
az "alkarakterlánccal". Nem egyezik. - Lépjen a 26. pozícióba. Hasonlítsa össze
trin
az "alkarakterlánccal". Nem egyezik. - Lépjen a 27. pozícióba. Hasonlítsa össze
ring
az "alkarakterlánccal". Talált egyezést, rekordpozíció 27.
Az "alkarakterlánc" a szöveg 27. pozíciójában található.
Példakód C++ nyelven
Ebben a példában a textSearch
függvény a "substring" részkarakterlánc pozícióinak megkeresésére szolgál a szövegben. Az eredmény egy vektor lesz, amely a mérkőzések kezdőpontjait tartalmazza.