Toutes les occurrences d'un facteur

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 3 — Boucles imbriquées et complexité quadratique

É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 $O (n p)$ .

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.