Construction directe d'un vecteur de suffixes compact et répétitions maximales

Un vecteur de suffixes d'un mot est une structure d'index équivalente à un arbre des suffixes. Elle a été introduite par Monostori en 2001. Il a proposé un algorithme linéaire de construction d'un vecteur étendu puis un autre algorithme linéaire pour transformer un vecteur étendu en un vecteur compact plus économique en espace. Nous commencerons par présenter cette structure et un algorithme de construction directe de sa version compacte permettant donc de manipuler des mots plus longs. Non seulement il est possible de construire directement un vecteur compact mais nous montrerons également que cette construction directe peut être plus rapide que la construction du vecteur étendu. Pour finir, nous verrons comment calculer efficacement les répétitions maximales en utilisant les vecteurs de sufixes.