Vers Boyer-Moore-Horspool⚓︎
L'idée est d'améliorer le code précédent (celui on parcourt le motif à l'envers) en sautant directement au prochain endroit potentiellement valide.
Pour cela on regarde le caractère X du texte sur lequel on s'est arrêté (car X n'était pas égal au caractère de rang équivalent dans le motif):
- si
Xn'est pas dans le motif, il est inutile de se déplacer "de 1" : on retomberait tout de suite surX, c'est du temps perdu. On se décale donc juste assez pour dépasserX, donc de la longueur du motif cherché. - si
Xest dans le motif (sauf à la dernière place du motif !), on va regarder la place de la dernière occurence deXdans le motif et de déplacer de ce nombre, afin de faire coïncider leXdu motif et leXdu texte.
Illustration de l'algorithme
Vous pouvez contrôler le déroulement de l'animation en la survolant avec la souris.
On dispose de la fonction dico_lettres :
```python linenums='1'
def dico_lettres(mot):
d = {}
for i in range(len(mot)-1):
d[mot[i]] = i
return d
*Exemple d'utilisation de la fonction ```BMH``` :*
```python
>>> BMH("une magnifique maison bleue", "maison")
[15]
>>> BMH("une magnifique maison bleue", "nsi")
[]
>>> BMH("une magnifique maison bleue", "ma")
[4, 15]
Code à trous 
```python linenums='1' def dico_lettres(mot): d = {} for i in range(len(mot)-1): d[mot[i]] = i return d
def BMH(texte, motif):
```
Code à trous :octicons-star-24:
```python linenums='1' def dico_lettres(mot): d = {} for i in range(len(mot)-1): d[mot[i]] = i return d
def BMH(texte, motif): dico = ... indices = ... i = ... while ...: k = ... while ...: ... if ...: ... ... else: if ...: ... else: ...
return ...
```
Code à trous :octicons-star-24: :octicons-star-24:
```python linenums='1' def dico_lettres(mot): d = {} for i in range(len(mot)-1): d[mot[i]] = i return d
def BMH(texte, motif): dico = ... indices = ... i = ... while i <= ... : k = ... while ... and ...: ... if k == ...: ... ... else: if ... in dico: ... else: ...
return ...
```
Code à trous :octicons-star-24: :octicons-star-24: :octicons-star-24:
```python linenums='1' def dico_lettres(mot): d = {} for i in range(len(mot)-1): d[mot[i]] = i return d
def BMH(texte, motif): dico = dico_lettres(motif) indices = [] i = 0 while i <= ... - ...: k = ... while k >= 0 and texte[...] == motif[...]: k = ... if k == ...: indices.append(...) i = ... else: if ... in dico: i += ... - ... - 1 else: i += ...
return ...
```