Algorithme de Boyer-Moore simplifié
Recherche de motif dans un texte
Enonce
Implémenter la version simplifiée de Boyer-Moore avec la règle du mauvais caractère. Retourner l'indice de la première occurrence du motif, ou -1.
Signature attendue
def boyer_moore(texte: str, motif: str) -> int:Exemples
boyer_moore("ABAAABCDABC", "ABC")→4boyer_moore("ABAAABCDABC", "XYZ")→-1boyer_moore("ABAAABCDABC", "AAAB")→2
📖 Rappel de cours
L'algorithme de Boyer-Moore recherche un motif dans un texte en comparant de droite à gauche. La règle du mauvais caractère permet de sauter des positions.
Règle du mauvais caractère :
Si le caractère du texte ne correspond pas, on décale le motif pour aligner la dernière occurrence de ce caractère dans le motif.
Complexité :
Pire cas : $O(n \cdot m)$ | Cas moyen : $O(n / m)$ (sub-linéaire !)
← Exercices d'algorithmique en Python — tris, dichotomie, récursivité
Exercices du meme theme
- Recherche dans une Liste Chaînée
- Pile et File
- Évaluation d'Expressions Postfixées
- Algorithme glouton : rendu de monnaie
- Sac à dos (Programmation Dynamique)
- Plus Longue Sous-séquence Commune (LCS)
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.