Recherche d'occurrences d'une chaîne de caractères dans une autre

(1) L'algorithme de Knuth-Morris-Pratt

Un automate qui effectue la recherche du suffixe-préfixe

Le précalcul

(du plus long préfixe de C qui est aussi suffixe de C1,...,Ci)
Peut se faire facilement en temps O(m2) mais ce n'est pas optimal

(2) L'algorithme de Boyer et Moore: l'idée

L'algorithme de Boyer et Moore: un peu de détail

Pour trouver les positions où une occurrence de C pourrait terminer

Récupération après un échec

et aussi redémarrage après une réussite quand on veut trouver toutes les occurrences
On a déjà trouvé un suffixe de C (disons xyz) qui termine à une position p en T
mais les prochaines caractères à gauche dans C et T sont différents; il y a trois cas:
Temps de calcul




File translated from TEX by TTH, version 3.05.
On 19 Dec 2006, 17:15.