Livre_silo 30 août 2013 16:32 Page 159
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
159
6 – Notions de complexité et algorithmique sur les tableaux
On effectue la recherche avec une boucle for, qui va considérer toutes les positions possibles
pour le mot m, c’est-à-dire tous les indices i entre 0 et len(t) - len(m), au sens large.
def recherche_mot(m, t):
for i in range(1 + len(t) - len(m)):
On teste si le mot m apparaît à la position i avec une seconde boucle, qui compare les
caractères de m et de t un à un. On utilise une variable j pour cela et on s’arrête, soit
lorsque j atteint len(m), soit lorsque les caractères diffèrent :
j = 0
while j < len(m) and m[j] == t[i + j]:
j += 1
Il est important de noter que le caractère paresseux du and est encore ici crucial : il évite
l’accès en dehors des bornes du tableau lorsque j atteint len(m). Une fois sorti de la boucle
while, on a reconnu le mot m à la position i si et seulement si j == len(m), auquel cas on renvoie i. On interrompt ainsi l’exécution de la fonction dès la première occurrence trouvée :
if j == len(m):
return i
Sinon, on passe à la valeur suivante de i. Si on parvient à la fin de la boucle for principale,
c’est qu’il n’y a pas d’occurrence de m dans t, ce que l’on signale en renvoyant None :
return None
Le code complet est donné programme 2 ci-dessous.
Le pire des cas de cet algorithme correspond à la situation où on cherche sans succès le
mot m à toutes les positions possibles dans t et où la boucle while parcourt néanmoins
tous les caractères de m. C’est le cas par exemple lorsque l’on recherche le mot X . . . XY
dans un texte constitué uniquement de X. La complexité dans le pire des cas est donc
|m| × (|t| − |m| + 1). Dans le meilleur des cas, la complexité est clairement |m|.
PROGRAMME 2 Recherche d’un mot dans un texte
def recherche_mot(m, t):
"""renvoie, si elle existe, la position de la première occurrence du mot m
dans le texte t et renvoie None sinon"""
for i in range(1 + len(t) - len(m)):
j = 0
while j < len(m) and m[j] == t[i + j]:
j += 1
if j == len(m):
return i
return None
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
159
6 – Notions de complexité et algorithmique sur les tableaux
On effectue la recherche avec une boucle for, qui va considérer toutes les positions possibles
pour le mot m, c’est-à-dire tous les indices i entre 0 et len(t) - len(m), au sens large.
def recherche_mot(m, t):
for i in range(1 + len(t) - len(m)):
On teste si le mot m apparaît à la position i avec une seconde boucle, qui compare les
caractères de m et de t un à un. On utilise une variable j pour cela et on s’arrête, soit
lorsque j atteint len(m), soit lorsque les caractères diffèrent :
j = 0
while j < len(m) and m[j] == t[i + j]:
j += 1
Il est important de noter que le caractère paresseux du and est encore ici crucial : il évite
l’accès en dehors des bornes du tableau lorsque j atteint len(m). Une fois sorti de la boucle
while, on a reconnu le mot m à la position i si et seulement si j == len(m), auquel cas on renvoie i. On interrompt ainsi l’exécution de la fonction dès la première occurrence trouvée :
if j == len(m):
return i
Sinon, on passe à la valeur suivante de i. Si on parvient à la fin de la boucle for principale,
c’est qu’il n’y a pas d’occurrence de m dans t, ce que l’on signale en renvoyant None :
return None
Le code complet est donné programme 2 ci-dessous.
Le pire des cas de cet algorithme correspond à la situation où on cherche sans succès le
mot m à toutes les positions possibles dans t et où la boucle while parcourt néanmoins
tous les caractères de m. C’est le cas par exemple lorsque l’on recherche le mot X . . . XY
dans un texte constitué uniquement de X. La complexité dans le pire des cas est donc
|m| × (|t| − |m| + 1). Dans le meilleur des cas, la complexité est clairement |m|.
PROGRAMME 2 Recherche d’un mot dans un texte
def recherche_mot(m, t):
"""renvoie, si elle existe, la position de la première occurrence du mot m
dans le texte t et renvoie None sinon"""
for i in range(1 + len(t) - len(m)):
j = 0
while j < len(m) and m[j] == t[i + j]:
j += 1
if j == len(m):
return i
return None