L'algorithme de la rotation lexicographiquement minimale est une technique fondamentale en informatique, notamment dans le traitement des chaînes de caractères et des séquences, pour identifier la permutation cyclique d'une séquence qui apparaît en premier dans l'ordre lexicographique. Cette méthode est cruciale pour la normalisation des représentations cycliques, la comparaison d'objets cycliques et la résolution de divers problèmes de programmation compétitive.

Principe de l'Algorithme

L'algorithme utilise une approche basée sur deux pointeurs pour trouver l'indice de départ de la rotation minimale. Il compare efficacement deux rotations potentielles en parallèle et élimine celles qui sont manifestement plus grandes que l'autre. Le processus est itératif et maintient deux "candidats" pour le début de la séquence minimale.

Description Détaillée

1. Initialisation : On définit deux indices, debutCandidatA = 0 et debutCandidatB = 1, qui représentent les points de départ des deux rotations en cours d'évaluation. Un troisième compteur, decalageComparaison = 0, enregistre la longueur du préfixe commun entre les séquences débutant à debutCandidatA et debutCandidatB. La longueur de la séquence est n.
2. Comparaison Itérative : La boucle principale continue tant que les deux candidats sont valides (inférieurs à n) et que le décalage de comparaison est également valide.
   • Si les éléments à (debutCandidatA + decalageComparaison) % n et (debutCandidatB + decalageComparaison) % n sont identiques, cela signifie que les préfixes communs s'étendent. On incrémente decalageComparaison.
   • Si les éléments diffèrent :
     • Si l'élément de debutCandidatA est lexicographiquement plus grand que celui de debutCandidatB, la rotation commençant à debutCandidatA ne peut pas être la plus petite. debutCandidatA est alors avancé à debutCandidatA + decalageComparaison + 1, passant ainsi au-delà du point de divergence.
     • Inversement, si l'élément de debutCandidatB est plus grand, debutCandidatB est avancé à debutCandidatB + decalageComparaison + 1.
3. Réinitialisation et Correction : Après qu'un candidat a été avancé, decalageComparaison est réinitialisé à 0, car le nouveau point de départ n'a pas encore de préfixe commun établi avec l'autre candidat. Si debutCandidatA et debutCandidatB deviennent identiques après une avancée, debutCandidatB est incrémenté pour s'assurer que les deux candidats restent distincts.
4. Résultat : À la fin de la boucle, l'indice le plus petit entre debutCandidatA et debutCandidatB représente le point de départ de la rotation lexicographiquement minimale de la séquence.

Implémentation Générique en C++

Voici une implémentation générique de l'algorithme utilisant des templates, pemrettant de l'appliquer à diverses séquences comme des std::vector<int> ou std::string.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // Pour std::min

/**
 * @brief Trouve l'indice de départ de la rotation lexicographiquement minimale d'une séquence.
 * @tparam SequenceType Type de la séquence (ex: std::vector<int>, std::string).
 * @param sequence La séquence à analyser.
 * @return L'indice de départ de la rotation minimale.
 */
template <typename SequenceType>
int trouverRotationMinimale(const SequenceType& sequence) {
    int n = sequence.size();
    if (n == 0) return 0; // Gérer le cas de séquence vide

    int debutCandidatA = 0; // Premier indice potentiel de début
    int debutCandidatB = 1; // Deuxième indice potentiel de début
    int decalageComparaison = 0; // Longueur du préfixe commun trouvé

    // La boucle continue tant qu'il reste des candidats valides et un préfixe à comparer
    while (debutCandidatA < n && debutCandidatB < n && decalageComparaison < n) {
        // Accéder aux éléments de manière cyclique
        // Cela fonctionne pour std::vector et std::string
        if (sequence[(debutCandidatA + decalageComparaison) % n] == sequence[(debutCandidatB + decalageComparaison) % n]) {
            decalageComparaison++; // Les éléments correspondent, étendre le préfixe commun
        } else {
            // Mismatch: l'un des candidats est éliminé
            if (sequence[(debutCandidatA + decalageComparaison) % n] > sequence[(debutCandidatB + decalageComparaison) % n]) {
                // Le candidat A est lexicographiquement plus grand à ce point
                debutCandidatA += decalageComparaison + 1; // Avancer A au-delà du point de divergence
            } else {
                // Le candidat B est lexicographiquement plus grand à ce point
                debutCandidatB += decalageComparaison + 1; // Avancer B au-delà du point de divergence
            }
            decalageComparaison = 0; // Réinitialiser l'offset de comparaison

            // Si les candidats se rencontrent, avancer le second pour maintenir la distinction
            if (debutCandidatA == debutCandidatB) {
                debutCandidatB++;
            }
        }
    }

    // Le plus petit des deux indices restants est le début de la rotation minimale
    return std::min(debutCandidatA, debutCandidatB);
}

Applications

1. Artisanat (Problème de type "LoGu P1368")

Description : Étant donné une séquence de n entiers représentant les niveaux de "défaut" de blocs dans un artisanat. On ne peut effectuer qu'une opération : déplacer le bloc le plus à gauche à l'extrémité droite. L'objectif est de trouver la configuration la plus "belle" (lexicographiquement la plus petite) possible en appliquant cette opération de rotation.

Exemple de Code :

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

// Inclure la fonction trouverRotationMinimale<std::vector<int>> ici

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int n;
    std::cin >> n;
    std::vector<int> sequenceDeBlocs(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> sequenceDeBlocs[i];
    }

    int indiceDebutMin = trouverRotationMinimale(sequenceDeBlocs);

    for (int i = 0; i < n; ++i) {
        std::cout << sequenceDeBlocs[(indiceDebutMin + i) % n] << (i == n - 1 ? "" : " ");
    }
    std::cout << std::endl;
    return 0;
}

Exemple d'Entrée :

10
10 9 8 7 6 5 4 3 2 1

Exemple de Sortie :

1 10 9 8 7 6 5 4 3 2

2. Colliers Isomorphes (Problème de type "BZOJ1398")

Description : Deux colliers sont représentés par des chaînes de caractères. Déterminer si ces deux colliers sont en fait le même collier (c'est-à-dire si leurs représentations minimales sont identiques), et afficher la représentation minimale s'ils le sont.

Exemple de Code :

#include <iostream>
#include <string>
#include <vector> // Nécessaire si on utilise std::vector<char> pour string, sinon std::string suffit.
#include <algorithm>

// Inclure la fonction trouverRotationMinimale<std::string> ici

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::string collierA, collierB;
    std::cin >> collierA >> collierB;
    int n = collierA.length();

    int debutMinA = trouverRotationMinimale(collierA);
    int debutMinB = trouverRotationMinimale(collierB);

    bool sontIsomorphes = true;
    for (int i = 0; i < n; ++i) {
        if (collierA[(debutMinA + i) % n] != collierB[(debutMinB + i) % n]) {
            sontIsomorphes = false;
            break;
        }
    }

    if (sontIsomorphes) {
        std::cout << "Yes" << std::endl;
        for (int i = 0; i < n; ++i) {
            std::cout << collierA[(debutMinA + i) % n];
        }
        std::cout << std::endl;
    } else {
        std::cout << "No" << std::endl;
    }

    return 0;
}

Exemple d'Entrée :

2234342423
2423223434

Exemple de Sortie :

Yes
2234342423

3. Chaîne Étrange (Problème de type "BZOJ2176")

Description : Pour une chaîne de caractères donnée, trouver sa "chaîne étrange", définie comme la rotation lexicographiquement la plus petite de cette chaîne.

Exemple de Code :

#include <iostream>
#include <string>
#include <vector> // Nécessaire si on utilise std::vector<char> pour string, sinon std::string suffit.
#include <algorithm>

// Inclure la fonction trouverRotationMinimale<std::string> ici

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int n; // La taille n peut être lue mais est aussi dispo via string.length()
    std::cin >> n;
    std::string s;
    std::cin >> s;
         
    int indiceDebutMin = trouverRotationMinimale(s);
     
    for (int i = 0; i < n; ++i) {
        std::cout << s[(indiceDebutMin + i) % n];
    }
    std::cout << std::endl;
    return 0;
}

Exemple d'Entrée :

10
asdfasdfas

Exemple de Sortie :

asasdfasdf