|
Algorithme de RaitaL'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. DescriptionLe 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é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 Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ? |
