L'algorithme de recherche de texte est une méthode fondamentale dans le traitement de texte et la recherche d'informations. Cet algorithme nous permet de localiser et d'identifier les occurrences d'une sous-chaîne(ou d'un modèle) dans un plus grand morceau de texte.
Comment ça fonctionne
- Commencez par un plus grand morceau de texte(ou document) et une sous-chaîne à rechercher.
- Parcourez chaque caractère du texte de manière séquentielle.
- Comparez la sous-chaîne avec une partie du texte qui a la même longueur que la sous-chaîne. Si une correspondance est trouvée, enregistrez la position actuelle.
- Passez à la position suivante et continuez la comparaison.
Exemple
Considérez le texte : "Recherchons une sous-chaîne dans ce texte pour voir comment l'algorithme fonctionne."
Et la sous-chaîne à rechercher : "sous-chaîne"
- Commencez à la position 0. Comparez
Let'
avec "sous-chaîne". Aucune concordance. - Déplacez-vous en position 1. Comparez
et's
avec "sous-chaîne". Aucune concordance. - Déplacez-vous en position 2. Comparez
t's
" avec "sous-chaîne". Aucune correspondance. - Déplacez-vous en position 3. Comparez
's s
avec "sous-chaîne". Aucune concordance. - Déplacez-vous en position 4. Comparez
se
avec "sous-chaîne". Aucune concordance. - Déplacez-vous en position 5. Comparez
sea
avec "sous-chaîne". Aucune concordance. - Déplacez-vous en position 6. Comparez
earc
avec "sous-chaîne". Aucune concordance. - Déplacez-vous en position 7. Comparez
arch
avec "sous-chaîne". Aucune concordance. - Déplacez-vous en position 8. Comparez
rch
" avec " sous-chaîne ". Aucune correspondance. - Déplacez-vous en position 9. Comparez
ch w
avec "sous-chaîne". Aucune concordance. - Déplacez-vous en position 10. Comparez
h wi
avec "sous-chaîne". Aucune concordance. - Déplacez-vous à la position 11. Comparez "
wit
avec " sous-chaîne ". Aucune correspondance. - Déplacez-vous en position 12. Comparez
with
avec "sous-chaîne". Aucune concordance. - Déplacez-vous à la position 13. Comparez
ithi
avec "sous-chaîne". Aucune concordance. - Déplacez-vous à la position 14. Comparez
thin
avec "sous-chaîne". Aucune concordance. - Déplacez-vous à la position 15. Comparez
hinn
avec "sous-chaîne". Aucune concordance. - Déplacez-vous à la position 16. Comparez
in t
avec "sous-chaîne". Aucune concordance. - Déplacez-vous à la position 17. Comparez
n th
avec "sous-chaîne". Aucune concordance. - Déplacez-vous à la position 18. Comparez "
thi
avec " sous-chaîne ". Aucune correspondance. - Déplacez-vous à la position 19. Comparez
this
avec "sous-chaîne". Aucune concordance. - Déplacez-vous à la position 20. Comparez
his
" avec " sous-chaîne ". Aucune correspondance. - Déplacez-vous à la position 21. Comparez
is t
avec "sous-chaîne". Aucune concordance. - Déplacez-vous en position 22. Comparez
s te
avec "sous-chaîne". Aucune concordance. - Déplacez-vous à la position 23. Comparez
ubst
avec "sous-chaîne". Aucune concordance. - Déplacez-vous à la position 24. Comparez
bstr
avec "sous-chaîne". Aucune concordance. - Déplacez-vous à la position 25. Comparez
stre
avec "sous-chaîne". Aucune concordance. - Déplacez-vous à la position 26. Comparez
trin
avec "sous-chaîne". Aucune concordance. - Déplacez-vous à la position 27. Comparez
ring
avec "sous-chaîne". Correspondance trouvée, position d'enregistrement 27.
La sous-chaîne "substring" se trouve à la position 27 dans le texte.
Exemple de code en C++
Dans cet exemple, la textSearch
fonction est utilisée pour trouver les positions de la sous-chaîne "sous-chaîne" dans le texte. Le résultat sera un vecteur contenant les positions de départ des matchs.