Algorithmique du texte

Errata

Chapitre 1 : Outils

• Page 40, ligne -7 : « dans le cas où x = abbabaabbabaaa » doit être « dans le cas où x = abbabaabbabaaaabbabbaa ».

Chapitre 3 : Localisation avec fenêtre glissante

• Page 118, ligne 8 : « les décalages de longueur |z'| - |z| = turbo » doit être « les décalages de longueur inférieure à |z'| - |z| = turbo ».

Chapitre 7 : Alignements

• Page 224, ligne -13 : « (voir aussi section 6.7) » doit être « (voir aussi section 6.6) ».

Chapitre 8 : Motifs approchés

• Page 287, ligne 16-17 : « (ligne 7 de l'algorithme INÉG-FUSION) » doit être « (ligne 7 de l'algorithme L-INÉGALITÉS) ».
• Page 293, ligne 15 : « y = CAATAAGAGAA » doit être « y = CAATAATAGAA ».
• Page 297, ligne 19 : « une insertion à la fin de y[0..7] » doit être « une insertion à la fin de y[0..6] ».
• Page 303, ligne 25 (merci à Christiane Frougny) : les valeurs de code(x[i..i+l-1]) pour YW, WC, CQ, QP, PG et GK sont respectivement 379, 38, 261, 253, 112 et 165 (et non pas 378, 361, 33, 272, 245 et 108).
• Page 303, ligne 28 et 29 (merci à Christiane Frougny) : les codes considérés sont dans l'ordre croissant 38, 112, 165, 253, 261 et 379 (et non pas 38, 108, 245, 272, 361 et 378) et leurs positions respectives sont {2}, {5}, {6}, {4}, {3} et {1}.
• Page 303, ligne 33 (merci à Christiane Frougny) : les valeurs de code(y[j..j+l-1]) pour LA, AW, WY, YQ, QQ, QK, KP, PG, GK et KA sont respectivement 9, 360, 399, 279, 273, 173, 248, 112, 165 et 8 (et non pas 180, 18, 379, 393, 273, 268, 172, 245, 108 et 160).
• Page 305, ligne -10 : L'algorithme L-DIFF-ANC est la version de l'algorithme L-DIFF-DIAG qui calcule les ancêtres communs en temps constant grâce au prétraitement de l'arbre compact des suffixes du mot z = x$y.

Chapitre 9 : Périodes locales

• Page 327, ligne -2 : « une position sur u², v² et w² sur y » doit être « une position de u², v² et w² sur y ».
• Page 328, ligne 1 : « la plus grande position sur au plus deux mots de E » doit être « la plus grande position d'au plus deux mots de E ».
• Page 328, ligne 3 : « position sur aucun mot » doit être « position d'aucun mot ».
• Page 328, ligne 5 : « la plus grande position que sur au plus un mot de E » doit être « la plus grande position que d'au plus un mot de E ».

Erreurs typographiques

Chapitre 1 : Outils

• Page 1, ligne 9 (merci à Laurent Mouchard) : « des ces aspects » doit être « de ces aspects ».
• Page 23, ligne -11 : « En notant s est le maximum » doit être « En notant s le maximum ».
• Page 49, ligne 16 : « des implantations efficaces pour solutions élémentaires » doit être « des implantations efficaces pour des solutions élémentaires ».

Chapitre 2 : Automates de localisation

• Page 74, ligne 4 : « chacune de ses deux opérations » doit être « chacune de ces deux opérations ».
• Page 95, lignes 12 et 13 : « ses implantation particulière » doit être « ses implantations particulières ».

Chapitre 3 : Localisation avec fenêtre glissante

• Page 103, ligne -5 : « w <_suff v aw <=_suff x » doit être « w <_suff v, aw <=_suff x »

Chapitre 4 : Table des suffixes

• Page 156, ligne -19 : « DÉF-LPC-SUF » doit être « DÉF-LPC-SUFF ».
• Page 159, ligne 22 : « suppression... » doit être « suppression, ... ».

Chapitre 6 : Index

• Page 209, ligne 2 : « En recvanche » doit être « En revanche ».

Chapitre 7 : Alignements

• Page 232, ligne -5 (merci à Arnaud Lefebvre) : « Dél(x[i] » doit être « Dél(x[i]) ».
• Page 261, ligne 20 : « le langage définit par » doit être « le langage défini par ».

Chapitre 8 : Motifs approchés

• Page 285, ligne -7 : « Le prétraitement du mot vient s'ensuit » doit être « Le prétraitement du mot vient à la suite ».
• Page 295, ligne -6, page 298, ligne 14 et page 298, ligne -2 : « R¹_j[i] = 1 » doit être « R¹_j[i] = 1 ».
• Page 295, ligne -5 : « Il se déduit l'étude » doit être « Il se déduit de l'étude ».

Chapitre 9 : Périodes locales

• Page 322, ligne 11 : « chaque position i » doit être « chaque position i ».

Bibliographie

• Page 339, ligne -1 : « The MIT Press, 2000 » doit être « The MIT Press, 2000. »