Algorithme de Raita
L'algorithme de Raita est un algorithme de recherche de sous-chaîne publié par Tim Raita en 1992. Il consiste en une variation de l'algorithme de Boyer-Moore-Horspool pour en améliorer la performance. En pratique, Raita est plus rapide que Boyer-Moore-Horspool sur de très grands textes, ou des alphabets réduits tel l'ADN.
On notera T le texte de recherche, P la sous-chaîne recherchée et ∑ l'alphabet.
Description modifier
Le pré-traitement de la sous-chaîne P est identique à Boyer-Moore.
Comme Boyer-Moore-Horspool la comparaison commence au dernier caractère, mais deux autres comparaisons sont ensuite effectuées, au premier caractère puis au caractère milieu, avant de comparer le reste des caractères.
Complexité modifier
En espace, Raita a une complexité O(|∑|).
Le pré-traitement a une complexité en temps en O(|P|+|∑|).
La recherche a une complexité en temps en O(|T|*|P|).
Implémentation modifier
