Discussion:Algorithme de Boyer-Moore-Horspool
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Cet article est indexé par le projet Informatique théorique.
Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.
| Avancement | Importance | pour le projet | |
|---|---|---|---|
| Ébauche | À évaluer |  | Informatique théorique (discussion • critères • liste • stats • hist. • comité • stats vues) |
Cet article ne comporte pas de liste de tâches suggérées. Vous pouvez saisir une liste de tâches à accomplir (par exemple sous forme d'une liste à puces), puis sauvegarder. Vous pouvez aussi consulter la page d'aide.
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)