NSI algos de tri

Contrairement à l'algorithme naïf qui, lui, ne fait ques tester pour chaque caractère et les x-1 suivants, x étant la taille du motif, si ils correspondent au motif, l'algorithme de Boyer-Moore est optimisé de plusieurs manières. Premièrement, il compare à partir du dernier caractère du motif et fait un prétraitement pour pouvoir se déplacer de x-(x-index_de_parcours_du_motif) d'un coup si l'on tombe sur un caractère qui n'est pas dans le motif et qui se décale de t en t si il reste un t dans le non déjà parcouru et que le motif n'a pas encore été trouvé. En somme, l'algorithme Boyer-Moore, au prix d'un prétraitement du motif, parcours le motif et le texte en même temps pour passer si il tombe sur un caractère hors-motif dans le texte et passer toute la partie du motif entre deux caractères identiques quand ce même caractère est trouvé dans le texte. Petit comparatif pour un motif de taille 20:

BOYER_MOORE! 10 000 caractères en 0.001995086669921875 secondes. ( 0 résultats )
NAIF! 10 000 caractères en 0.003991842269897461 secondes. ( 0 résultats )


BOYER_MOORE! 100 000 caractères en 0.010976791381835938 secondes. ( 0 résultats )
NAIF! 100 000 caractères en 0.024932146072387695 secondes. ( 0 résultats )


BOYER_MOORE! 1 000 000 caractères en 0.1176915168762207 secondes. ( 0 résultats )
NAIF! 1 000 000 caractères en 0.2552926540374756 secondes. ( 0 résultats )