Aller au contenu

Vers la recherche textuelle naïve⚓︎

Illustration de l'algorithme

image

É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 :

🐍 Script Python
>>> 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 ⭐ ⭐ ⭐ ⭐
🐍 Script Python
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 ⭐ ⭐ ⭐
🐍 Script Python
 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 ⭐ ⭐
🐍 Script Python
 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 ⭐
🐍 Script Python
 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 ...