Discussion:Algorithme de Boyer-Moore-Horspool
Dernier commentaire : il y a 3 ans par 127.0.0.1
Autres discussions [liste]
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
L'algorithme présenté ici, comporte une boucle infinie. Cas de test:
text: "lorem ipsum" pattern: "ipsum"
Dans ce cas skip_table['m'] vaut 0.
Dans la boucle while, le test text[i + psize - 1] == pattern[psize - 1]
vaut true
; le "m" de "ipsum" correspond au "m" de "lorem".
La comparaison suivante memcmp(...) échoue car "lorem" est différent de "ipsum".
L'instruction suivante incrémente i avec la valeur de skip_table["m"] qui vaut 0.
Par conséquent, la boucle while boucle indéfiniment.
Proposition de modification en C:
int inc = 0;
while( i <= tsize - psize ) {
inc = skip_table[ (int) text[ i + psize - 1 ] ];
if( inc == 0 ) { /* les lettres sont identiques */
if (memcmp(text + i, pattern, psize - 1) == 0)
return i;
inc = 1;
}
i += inc;
}
— Le message qui précède, non signé, a été déposé par l'IP 127.0.0.1 (discuter), le 1 mars 2021 à 13:38 (CET)