Algorithme de Raita

L'algorithme de Raita est un algorithme de recherche de sous-chaîne publié par Tim Raita en 1992. Il est 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 sur des alphabets réduits tel l'ADN.

Dans la suite, on notera T le texte de recherche, P la sous-chaîne recherchée et ∑ l'alphabet.

Description

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é

La complexité en espace de l'algorithme est O(|Σ|), le pré-traitement a une complexité en temps en O(P+|Σ|) et la recherche a une complexité en temps en O(|T|×|Σ|).

Animation