Aller au contenu

Vers la recherche textuelle naïve⚓︎

Illustration de l'algorithme

Écrire une fonction recherche_naive qui prend en paramètres deux chaines de caractères texte et motif et qui renvoie la liste des indices (éventuellement vide) des occurrences de la chaîne motif dans la chaîne texte.

Exemple d'utilisation : 

>>> recherche_naive("une magnifique maison bleue", "maison")
[15]
>>> recherche_naive("une magnifique maison bleue", "nsi")
[]
>>> recherche_naive("une magnifique maison bleue", "ma")
[4, 15]

Code à trous ⭐ ⭐ ⭐ ⭐ 
1
2
3
4
5
def recherche_naive(texte, motif):
    '''
    renvoie la liste des indices (éventuellement vide) des occurrences de
    de la chaîne `motif` dans la chaîne `texte`.
    '''
Code à trous ⭐ ⭐ ⭐ 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def recherche_naive(texte, motif):
    '''
    renvoie la liste des indices (éventuellement vide) des occurrences de
    de la chaîne `motif` dans la chaîne `texte`.
    '''
    indices = ...
    i = ...
    while ...:
        ...
        while ...:
            ...
        if ...:
            ...
        ...

    return ...
Code à trous ⭐ ⭐ 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def recherche_naive(texte, motif):
    '''
    renvoie la liste des indices (éventuellement vide) des occurrences de
    de la chaîne `motif` dans la chaîne `texte`.
    '''
    indices = ...
    i = ...
    while i <= ...:
        k = ...
        while k < ... and ...:
            ...
        if ...:
            indices.append(...)
        i += ...

    return ...
Code à trous ⭐ 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def recherche_naive(texte, motif):
    '''
    renvoie la liste des indices (éventuellement vide) des occurrences de
    de la chaîne `motif` dans la chaîne `texte`.
    '''
    indices = []
    i = 0
    while i <= ... - ...:
        k = ...
        while k < len(...) and texte[...] == motif[...]:
            k += ...
        if k == len(...):
            indices.append(...)
        i += ...

    return ...