informatique (tronc commun des prépas scientifiques) · Chapitre 3 · Application directe du cours
Toutes les occurrences d'un facteur
Boucles imbriquées et complexité quadratique · niveau 1 (application)
Énoncé
Écrire une fonction positions_facteur(m, s) qui renvoie la liste de toutes les positions où le motif m débute dans le texte s (y compris en cas de chevauchements). Tester sur positions_facteur("aa", "aaaa").
Corrigé
def positions_facteur(m: str, s: str) -> list:
pos = []
n, p = len(s), len(m)
for i in range(n - p + 1):
j = 0
while j < p and s[i + j] == m[j]:
j += 1
if j == p:
pos.append(i) # On mémorise la position sans arrêter la boucle
return pos
assert positions_facteur("aa", "aaaa") == [0, 1, 2]
assert positions_facteur("ana", "banane") == [1, 3]La complexité de l'algorithme est en .
Exercices semblables
- Compter les inversions corrigé
- Le pire cas de la recherche de facteur, exactement corrigé
- Le tri à bulles ne déplace qu'à petits pas corrigé
- Compter les tours corrigé
- Tous distincts ? corrigé