Un tableau de préfixes, souvent appelé tableau de suffixes, est une structure de données essentielle pour la manipulation efficace des sous-chaînes d'une chaîne de caractères donnée. Il permet de résoudre divers problèmes liés aux sous-chaînes en exploitant l'ordre lexicographique des suffixes de la chaîne.

Définition et Principe :

• La comparaison entre deux chaînes se fait selon l'ordre lexicographique. Si les chaînes diffèrent à une certaine position, celle qui a le caractère le plus petit à cette position est considérée comme lexicographiquement plus petite. Une chaîne vide est plus petite que n'importe quelle autre chaîne.
• L'ensemble de toutes les sous-chaînes d'une chaîne est équivalent à l'ensemble des préfixes de tous ses suffixes.
• Pour traiter efficacement les sous-chaînes, la première étape consiste à trier tous les suffixes de la chaîne selon leur ordre lexicographique.

Tableau de Préfixes :

Le tableau de préfixes (Suffix Array, SA) représente l'ordre trié des suffixes. Plus précisément, il s'agit d'un tableau sa[i] indiquant que le i-ème suffixe le plus petit commence à l'indice sa[i] de la chaîne originale. Pour faciliter les calculs, on maintient également un tableau rk[i] qui représente le rang du suffixe commençant à l'indice i.

Algorithme de Construction par Duplication Progressive :

L'idée est de trier les suffixes par blocs de longueur croissante : d'abord par blocs de longueur 1, puis de longueur 2, puis de longueur 4, et ainsi de suite, jusqu'à ce que la longueur des blocs soit supérieure ou égale à la longueur de la chaîne. Si l'on connaît le classement des suffixes par blocs de longueur w, on peut classer les suffixes par blocs de longueur 2w en considérant chaque suffixe comme une paire de blocs : le bloc de tête de longueur w et le bloc de queue de longueur w.

Processus de Tri :

Tri par Base (Radix Sort) : Pour trier ces paires de blocs, on utilise le tri par base. Un nombre représenté en base b est comparé selon ses chiffres, de la position la plus significative à la moins significative. Ici, les "chiffres" sont les rangs des blocs.

Tri par Comptage (Counting Sort) : Chaque "chiffre" (rang) est trié individuellement à l'aide du tri par comptage. On compte les occurrences de chaque rang, puis on calcule les sommes cumulées pour déterminer la position finale de chaque élément. Pour préserver l'ordre relatif des éléments de même valeur et pour pouvoir supprimer les éléments déjà traités, il est nécessaire de parcourir le tableau en sens inverse lors de l'attribution des rangs.

Preuve de Correction :

En triant d'abord par le chiffre le moins significatif (bloc de droite) puis par le chiffre le plus significatif (bloc de gauche), l'ordre établi par le tri du chiffre de droite est préservé pour les paires ayant le même chiffre de gauche. Cela garantit que le tri global est correct. La complexité est de O(N log N), où N est la longueur de la chaîne.

Optimisations :

• On n'a pas besoin de trier explicitement le "deuxième critère" (le bloc de droite) car le tableau est déjà partiellement trié par blocs de longueur w. On peut déduire l'ordre basé sur le deuxième critère et n'effectuer qu'un seul tri par comptage.
• L'algorithme peut s'arrêter plus tôt si le nombre de rangs distincts atteint N, signifiant que tous les suffixes sont déjà disitnctement classés.

Extrait de Code (Construction du SA) :

int n; // Longueur de la chaîne
std::string s;
std::vector<int> sa, rk, height; // sa: Suffix Array, rk: Rang, height: LCP array

void buildSuffixArray() {
    n = s.length();
    sa.resize(n);
    rk.resize(n);
    std::vector<int> tmp_rk(n);
    std::vector<int> count(std::max(n, 256)); // Pour le comptage

    // Initialisation avec les caractères individuels (rangs de longueur 1)
    for (int i = 0; i < n; ++i) {
        rk[i] = s[i];
    }

    for (int k = 1; k < n; k *= 2) {
        // Tri par le deuxième critère (suffixe décalé de k)
        std::vector<int> suffixes_to_sort;
        for (int i = 0; i < n; ++i) {
            if (i + k < n) {
                suffixes_to_sort.push_back(i);
            }
        }
        // On trie les suffixes qui ont un "deuxième critère"

        // Tri par le premier critère (rang actuel)
        // Utilisation du tri par comptage pour les deux critères de manière combinée
        
        // Réorganisation basée sur les paires (rk[i], rk[i+k])
        // Cette partie est complexe et nécessite une implémentation précise du radix sort
        // pour les paires. Une approche courante est d'abord de trier par rk[i+k] puis par rk[i].
        
        // Après le tri, on recalcule les rangs tmp_rk
        // tmp_rk[sa[0]] = 0;
        // for (int i = 1; i < n; ++i) {
        //     bool same_pair = (rk[sa[i]] == rk[sa[i - 1]]) && 
        //                      (sa[i] + k < n ? (sa[i - 1] + k < n ? rk[sa[i] + k] == rk[sa[i - 1] + k] : false) : (sa[i-1]+k < n ? false : true) );
        //     tmp_rk[sa[i]] = tmp_rk[sa[i - 1]] + (same_pair ? 0 : 1);
        // }
        // rk = tmp_rk;

        // Si tous les rangs sont uniques, on a terminé
        // if (rk[sa[n - 1]] == n - 1) break;
    }
    // Le code ci-dessus est une esquisse. Une implémentation complète du radix sort sur les paires est nécessaire.
}

Utilisation Simple : Recherche de Sous-chaînes

Puisque les suffixes sont triés, les suffixes commençant par une sous-chaîne donnée apparaîtront consécutivement dans le tableau de préfixes. On peut donc utiliser une recherche binaire sur le tableau de préfixes pour trouver la plage des suffixes qui commencent par la sous-chaîne recherchée, permettant ainsi de compter ses occurrences ou de trouver ses positions.

Propriété Clé : LCP Array

Le tableau LCP (Longest Common Prefix) height[i] stocke la longueur du plus long préfixe commun entre le i-ème suffixe trié (sa[i]) et le (i-1)-ème suffixe trié (sa[i-1]). La propriété cruciale est que le plus long préfixe commun entre deux suffixes quelconques sa[i] et sa[j] (avec i < j) est le minimum des valeurs LCP entre les suffixes consécutifs dans cet intervalle : LCP(sa[i], sa[j]) = min(height[k] for k from i+1 to j). Cette propriété permet de calculer le LCP entre deux suffixes en O(1) après avoir précalculé le tableau LCP et utilisé une structure comme une table de préfixes (ST table).

Calcul du Tableau LCP (Algorithme de Kasai) :

Une propriété importante pour calculre le tableau LCP est la suivante : pour deux suffixes consécutifs dans l'ordre original i et i-1, leurs rangs respectifs dans le tableau de préfixes sont rk[i] et rk[i-1]. On a la relation : height[rk[i]] ≥ height[rk[i-1]] - 1. Cette propriété permet de calculer les valeurs LCP de manière linéaire. On itère sur les suffixes dans l'ordre de la chaîne originale (indice i). Si k est la valeur LCP calculée pour le suffixe précédent (i-1), alors le LCP pour le suffixe i commencera au moins à k-1.

La complexité de ce calcul est O(N).

Extrait de Code (Calcul du LCP Array) :

void buildLCPArray() {
    height.resize(n);
    int k = 0; // Longueur courante du LCP
    for (int i = 0; i < n; ++i) {
        if (rk[i] == 0) { // Le premier suffixe dans l'ordre trié a un LCP de 0 avec le précédent (inexistant)
            k = 0;
            continue;
        }
        // On récupère l'indice du suffixe qui précède le suffixe i dans l'ordre trié
        int j = sa[rk[i] - 1]; 
        
        // On peut commencer la comparaison à partir de k-1 (s'il est positif)
        if (k > 0) {
            k--;
        }

        // On étend le LCP tant que les caractères correspondent et qu'on reste dans les limites de la chaîne
        while (i + k < n && j + k < n && s[i + k] == s[j + k]) {
            k++;
        }
        height[rk[i]] = k; // LCP entre sa[rk[i]] et sa[rk[i]-1]
    }
}

Applications :

• Comparaison de Sous-chaînes : En connaissant le LCP de deux sous-chaînes, on peut déterminer leur ordre lexicographique en comparant simplement le premier caractère après le LCP commun. Cela permet des comparaisons en O(1).
• Nombre de Sous-chaînes Uniques : Le nombre total de sous-chaînes d'une chaîne de longueur N est N(N+1)/2. Pour obtenir le nombre de sous-chaînes uniques, on soustrait les répétitions. Chaque valeur height[i] représente le nombre de sous-chaînes qui sont répétées entre sa[i] et sa[i-1]. Ainsi, le nombre de sous-chaînes uniques est : N(N+1)/2 - sum(height[i] for i from 1 to N-1).

Note : L'implémentation du tri par base pour le tableau de préfixes est souvent délicate. Le code fourni est une illustration et nécessite une mise en œuvre complète du tri par base sur des paires de valeurs.