O algoritmo Text Search é um método fundamental no processamento de texto e recuperação de informações. Esse algoritmo nos permite localizar e identificar ocorrências de uma substring(ou padrão) em um trecho maior de texto.
Como funciona
- Comece com um pedaço maior de texto(ou documento) e uma substring para pesquisar.
- Percorra cada caractere do texto sequencialmente.
- Compare a substring com uma parte do texto que tem o mesmo comprimento que a substring. Se for encontrada uma correspondência, registre a posição atual.
- Mova para a próxima posição e continue a comparação.
Exemplo
Considere o texto: "Vamos procurar uma substring neste texto para ver como o algoritmo funciona."
E a substring a ser pesquisada: "substring"
- Comece na posição 0. Compare
Let'
com "substring". Nenhuma correspondência. - Mover para a posição 1. Compare
et's
com "substring". Nenhuma partida. - Mover para a posição 2. Compare
t's
" com "substring". Nenhuma correspondência. - Mover para a posição 3. Compare
's s
com "substring". Nenhuma partida. - Mover para a posição 4. Compare
se
com "substring". Nenhuma partida. - Mover para a posição 5. Compare
sea
com "substring". Nenhuma correspondência. - Mover para a posição 6. Compare
earc
com "substring". Nenhuma partida. - Mover para a posição 7. Compare
arch
com "substring". Nenhuma correspondência. - Mover para a posição 8. Compare
rch
" com "substring". Nenhuma correspondência. - Mover para a posição 9. Compare
ch w
com "substring". Nenhuma correspondência. - Mover para a posição 10. Compare
h wi
com "substring". Nenhuma correspondência. - Mover para a posição 11. Compare "
wit
com "substring". Nenhuma correspondência. - Mover para a posição 12. Compare
with
com "substring". Nenhuma correspondência. - Mover para a posição 13. Compare
ithi
com "substring". Nenhuma partida. - Mover para a posição 14. Compare
thin
com "substring". Nenhuma partida. - Mover para a posição 15. Compare
hinn
com "substring". Nenhuma correspondência. - Mover para a posição 16. Compare
in t
com "substring". Nenhuma partida. - Mover para a posição 17. Compare
n th
com "substring". Nenhuma correspondência. - Mover para a posição 18. Compare "
thi
com "substring". Nenhuma correspondência. - Mover para a posição 19. Compare
this
com "substring". Nenhuma correspondência. - Mover para a posição 20. Compare
his
" com "substring". Nenhuma correspondência. - Mover para a posição 21. Compare
is t
com "substring". Nenhuma correspondência. - Mover para a posição 22. Compare
s te
com "substring". Nenhuma partida. - Mover para a posição 23. Compare
ubst
com "substring". Nenhuma correspondência. - Mover para a posição 24. Compare
bstr
com "substring". Nenhuma correspondência. - Mover para a posição 25. Compare
stre
com "substring". Nenhuma correspondência. - Mover para a posição 26. Compare
trin
com "substring". Nenhuma correspondência. - Mover para a posição 27. Compare
ring
com "substring". Correspondência encontrada, posição de registro 27.
A substring "substring" é encontrada na posição 27 dentro do texto.
Exemplo de código em C++
Neste exemplo, a textSearch
função é usada para encontrar as posições da substring "substring" dentro do texto. O resultado será um vetor contendo as posições iniciais das partidas.