Solution de Recherche de motif dans un texte - Sujet 31 - EP NSI 2025

Résoudre ce problème
Moyen Officiel
Python (3.14.0)

Énoncé du problème

EXERCICE 1 (10 points)

Écrire une fonction recherche_motif qui prend en paramètre une chaîne de caractères motif non vide et une chaîne de caractères texte et qui renvoie la liste des positions de motif dans texte. Si motif n’apparaît pas, la fonction renvoie une liste vide.

Exemples:

>>> recherche_motif("ab", "")
[]
>>> recherche_motif("ab", "cdcdcdcd")
[]
>>> recherche_motif("ab", "abracadabra")
[0, 7]
>>> recherche_motif("ab", "abracadabraab")
[0, 7, 11]

EXERCICE 2 (10 points)

Dans cet exercice, on considère un graphe non orienté représenté sous forme de listes d’adjacence. On suppose que les sommets sont numérotés de 0 à n-1.

Ainsi, le graphe suivant:

flowchart TD
    n3([3]) --- n1([1])
    n0([0]) --- n1
    n0 --- n2([2])
    n4([4]) --- n5([5])

[Figure : schéma d’un graphe non orienté à six sommets dessinés dans des ovales, répartis sur deux rangées : en haut, de gauche à droite, les sommets 3, 0 et 4 ; en bas, de gauche à droite, les sommets 1, 2 et 5. Les arêtes tracées relient 3 à 1, 0 à 1, 0 à 2, et 4 à 5.]

sera représenté par la liste d’adjacence suivante:

adj = [[1, 2], [0, 3], [0], [1], [5], [4]]

On souhaite déterminer les sommets accessibles depuis un sommet donné dans le graphe. Pour cela, on va procéder à un parcours en profondeur du graphe.

Compléter la fonction suivante.

def parcours(adj, x, acc):
    '''Réalise un parcours en profondeur récursif
    du graphe donné par les listes d'adjacence adj
    depuis le sommet x en accumulant les sommets
    rencontrés dans acc'''
    if x ...:
        acc.append(x)
        for y in ...:
            parcours(adj, ...)

def accessibles(adj, x):
    '''Renvoie la liste des sommets accessibles dans le
    graphe donné par les listes d'adjacence adj depuis
    le sommet x.'''
    acc = []
    parcours(adj, ...)
    return acc

Exemples :

>>> accessibles([[1, 2], [0, 3], [0], [1], [5], [4]], 0)
[0, 1, 3, 2]
>>> accessibles([[1, 2], [0, 3], [0], [1], [5], [4]], 4)
[4, 5]

Les contraintes ci-dessous sont ajoutées par la plateforme et ne font pas partie du sujet.

Exercice 1

Contraintes :

  • motif est une chaîne de caractères non vide : 1 <= len(motif) <= 100
  • texte est une chaîne de caractères éventuellement vide : 0 <= len(texte) <= 10^4
  • motif et texte ne contiennent que des caractères ASCII imprimables
  • Les positions renvoyées sont les indices de début d’occurrence dans texte, rangés dans l’ordre croissant
  • Les occurrences qui se chevauchent sont toutes comptées : recherche_motif("aa", "aaaa") renvoie [0, 1, 2]
  • Si len(motif) > len(texte), la liste renvoyée est vide

Exercice 2

Contraintes :

  • adj est une liste de n listes d’entiers avec 1 <= n <= 200
  • Les sommets sont numérotés de 0 à n-1 et 0 <= x <= n-1
  • Pour tout sommet u, adj[u] contient les voisins de u, chacun compris entre 0 et n-1
  • Le graphe est non orienté : v appartient à adj[u] si et seulement si u appartient à adj[v]
  • adj[u] ne contient ni doublon ni le sommet u lui-même
  • La valeur renvoyée est une liste dont l’ordre est significatif : les sommets y apparaissent dans l’ordre de leur première visite par le parcours en profondeur, chaque sommet étant ajouté à son entrée et les voisins étant explorés dans l’ordre où ils figurent dans adj[x]

Solution

Exercice 1 - recherche d’un motif dans un texte

L’idée. On veut toutes les positions où motif commence dans texte. Il suffit d’essayer chaque position de départ, l’une après l’autre : on se place en position i, on découpe dans texte un morceau de la même longueur que motif, et on regarde s’il est égal à motif. Si oui, on note i dans la liste résultat. Comme on avance de 1 en 1, les positions sortent déjà dans l’ordre croissant.

Un petit exemple. Pour recherche_motif("ab", "abracadabra") : en i = 0 le morceau est "ab", on garde 0 ; en i = 1 c’est "br", on ne garde rien ; … ; en i = 7 c’est à nouveau "ab", on garde 7. Résultat : [0, 7].

def recherche_motif(motif, texte):
    positions = []
    n = len(motif)
    # La dernière position de départ possible est len(texte) - n
    for i in range(len(texte) - n + 1):
        if texte[i:i + n] == motif:
            positions.append(i)
    return positions

positions accumule les réponses, n est la longueur du motif. La boucle s’arrête à len(texte) - n parce qu’au-delà il ne reste plus assez de caractères pour contenir le motif : le + 1 dans le range sert justement à ne pas oublier cette dernière position. Deux cas se règlent tout seuls, sans code particulier : si texte est vide, ou plus court que motif, le range est vide et on renvoie []. Et comme on avance de 1 et non de n, les occurrences qui se chevauchent sont toutes trouvées : recherche_motif("aa", "aaaa") renvoie [0, 1, 2].

Exercice 2 - parcours en profondeur d’un graphe

L’idée. Pour visiter tout ce qui est accessible depuis x, on note x comme rencontré, puis on recommence la même chose depuis chacun de ses voisins. C’est la récursivité : parcours s’appelle lui-même sur les voisins. Le seul danger est de tourner en rond, car dans un graphe non orienté on peut toujours revenir en arrière. D’où le test du début : on ne repart d’un sommet que s’il n’est pas déjà dans acc. La liste acc sert donc à deux choses à la fois : c’est le résultat que l’on construit, et c’est la mémoire des sommets déjà visités.

Un petit exemple. Avec adj = [[1, 2], [0, 3], [0], [1], [5], [4]] et x = 0 : on ajoute 0, on part chez son premier voisin 1, on ajoute 1, on part chez 0 qui est déjà vu donc on ne fait rien, puis chez 3 que l’on ajoute. On remonte alors jusqu’à 0 et on visite son deuxième voisin, 2. D’où [0, 1, 3, 2].

def parcours(adj, x, acc):
    '''Réalise un parcours en profondeur récursif
    du graphe donné par les listes d'adjacence adj
    depuis le sommet x en accumulant les sommets
    rencontrés dans acc'''
    # Si x est déjà dans acc, il a déjà été visité : on ne repart pas de lui
    if x not in acc:
        acc.append(x)
        for y in adj[x]:
            parcours(adj, y, acc)

def accessibles(adj, x):
    '''Renvoie la liste des sommets accessibles dans le
    graphe donné par les listes d'adjacence adj depuis
    le sommet x.'''
    acc = []
    parcours(adj, x, acc)
    return acc

Les trois trous se remplissent donc par x not in acc, adj[x] (la liste des voisins de x) et parcours(adj, y, acc) (on repart du voisin y, avec la même liste acc). Dans accessibles, on crée la liste vide et on lance parcours(adj, x, acc) : c’est bien la même liste qui est remplie pendant tous les appels, puisque append modifie la liste sur place, et c’est elle que l’on renvoie à la fin. Attention à l’ordre : acc.append(x) est fait à l’entrée dans le sommet, avant de descendre chez les voisins, et les voisins sont pris dans l’ordre où ils figurent dans adj[x]. C’est ce qui donne exactement [0, 1, 3, 2] et non un autre ordre. Pour x = 4, le parcours ne sort jamais de la partie du graphe formée par 4 et 5 : il renvoie [4, 5].