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 | modifier le code]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 | modifier le code]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 | modifier le code]
