Algoritmus Text Search je základní metodou při zpracování textu a vyhledávání informací. Tento algoritmus nám umožňuje lokalizovat a identifikovat výskyty podřetězce(nebo vzoru) v rámci většího kusu textu.
Jak to funguje
- Začněte s větším textem(nebo dokumentem) a podřetězcem, který chcete vyhledat.
- Postupně procházejte každý znak textu.
- Porovnejte podřetězec s částí textu, která má stejnou délku jako podřetězec. Pokud je nalezena shoda, zaznamenejte aktuální pozici.
- Přejděte na další pozici a pokračujte ve srovnání.
Příklad
Zvažte text: "Pojďme hledat podřetězec v tomto textu, abychom viděli, jak algoritmus funguje."
A podřetězec, který se má hledat: "podřetězec"
- Začněte na pozici 0. Porovnejte
Let'
s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 1. Porovnejte
et's
s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 2. Porovnejte
t's
" s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 3. Porovnejte
's s
s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 4. Porovnejte
se
s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 5. Porovnejte
sea
s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 6. Porovnejte
earc
s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 7. Porovnejte
arch
s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 8. Porovnejte
rch
" s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 9. Porovnejte
ch w
s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 10. Porovnejte
h wi
s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 11. Porovnejte "
wit
s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 12. Porovnejte
with
s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 13. Porovnejte
ithi
s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 14. Porovnejte
thin
s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 15. Porovnejte
hinn
s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 16. Porovnejte
in t
s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 17. Porovnejte
n th
s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 18. Porovnejte "
thi
s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 19. Porovnejte
this
s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 20. Porovnejte
his
" s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 21. Porovnejte
is t
s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 22. Porovnejte
s te
s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 23. Porovnejte
ubst
s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 24. Porovnejte
bstr
s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 25. Porovnejte
stre
s "podřetězcem". Žádná shoda. - Přejděte na pozici 26. Porovnejte
trin
s "podřetězcem". Žádná shoda. - Přesuňte se na pozici 27. Porovnejte
ring
s "podřetězcem". Shoda nalezena, rekordní pozice 27.
Podřetězec "podřetězec" se nachází na pozici 27 v textu.
Příklad kódu v C++
V tomto příkladu textSearch
se funkce používá k nalezení pozic podřetězce "podřetězec" v textu. Výsledkem bude vektor obsahující počáteční pozice zápasů.