Fonction Z (Tableau Z)

La fonction Z, souvent associée à l'algorithme d'extension KMP, permet de calculer pour chaque psoition i d'une chaîne de caractères, la longueur du plus long préfixe commun entre la chaîne entière et le suffixe commençant à i.

Par exemple, pour la chaîne "aaabaac", le tableau Z correspondant est [7, 2, 1, 0, 2, 1, 0].

Mécanisme de calcul

L'optimisation centrale de cet algorithme repose sur la maintenance d'une fenêtre de correspondance, similaire à l'algorithme de Manacher. On définit un indice de référence pivot et une limite droite borneMax. Le pivot correspond au début du segment qui possède la correspondance la plus à droite actuellement connue, et borneMax représente la fin de cette correspondance (pivot + Z[pivot]).

Lors du calcul de Z[i], plusieurs cas se présentent selon la position de i par rapport à borneMax :

1. i est en dehors de la fenêtre (i >= borneMax) : Aucune information préalable n'est exploitable. On effectue une comparaison naïve à partir de l'indice i.
2. i est dans la fenêtre (i < borneMax) : On peut utiliser la symétrie. La position correspondante dans le préfixe est i - pivot.
   • Si Z[i - pivot] est strictement inférieur à borneMax - i, la correspondance s'arrête avant la limite de la fenêtre. On a donc directement Z[i] = Z[i - pivot].
   • Si Z[i - pivot] atteint ou dépasse borneMax - i, la correspondance s'étend au-delà de la fenêtre connue. On initialise la longueur à borneMax - i et on tente d'étendre la correspondance par comparaison directe au-delà de borneMax.

Implémentation du tableau Z

L'implémentation suivante fusionne les cas de figure. La variable longueurInit récupère la valeur minimale garantie par la fenêtre actuelle. La boucle while étend ensuite cette longueur si possible, gérant ainsi nativement les cas d'extension.

void calculerTableauZ(const string& chaine, vector<int>& z) {
    int taille = chaine.length();
    z[0] = taille;
    int pivot = 0;
    int borneMax = 0;

    for (int i = 1; i < taille; ++i) {
        int longueurInit = 0;
        // Si i est couvert par la fenêtre, on exploite la symétrie
        if (i < borneMax) {
            longueurInit = min(borneMax - i, z[i - pivot]);
        }
        
        // Extension de la correspondance
        while (i + longueurInit < taille && chaine[i + longueurInit] == chaine[longueurInit]) {
            longueurInit++;
        }
        
        // Mise à jour de la fenêtre si une nouvelle limite droite est trouvée
        if (i + longueurInit > borneMax) {
            borneMax = i + longueurInit;
            pivot = i;
        }
        z[i] = longueurInit;
    }
}

Tableau d'extension (Tableau E)

Le tableau E généralise ce concept pour comparer deux chaînes distinctes. Pour un texte A et un motif B, E[i] représente la longueur du plus long préfixe commun entre A[i...] et B[0...].

La logique reste identique à celle du tableau Z, à la différence près que la symétrie s'appuie sur le tableau Z de la chaîne B. On maintient un centreA et une limiteA pour le texte A. La position miroir i - centreA est ensuite évaluée dans le tableau Z de B.

Implémentation du tableau E

// Nécessite le tableau Z de la chaîne 'motif' (B) préalablement calculé
void calculerTableauE(const string& texte, const string& motif, const vector<int>& zB, vector<int>& e) {
    int tailleA = texte.length();
    int tailleB = motif.length();
    int centreA = 0;
    int limiteA = 0;

    for (int i = 0; i < tailleA; ++i) {
        int longueurInit = 0;
        if (i < limiteA) {
            longueurInit = min(limiteA - i, zB[i - centreA]);
        }
        
        // Extension en comparant le texte A et le motif B
        while (i + longueurInit < tailleA && longueurInit < tailleB && texte[i + longueurInit] == motif[longueurInit]) {
            longueurInit++;
        }
        
        if (i + longueurInit > limiteA) {
            limiteA = i + longueurInit;
            centreA = i;
        }
        e[i] = longueurInit;
    }
}