Algorithme de Raita
# 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|).

