title: Algorithme de Raita
text: # 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
  
  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é
  
  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|).
  
  