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

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]

Énoncé du problème