Ce problème consiste à décompresser une chaîne de caractères représentant un message crypté extraterrestre. La compression utilise un format où des sous-chaînes répétées consécutives sont codées sous la forme [D X], avec D un entier entre 1 et 99 indiquant le nombre de répétitions, et X la sous-chaîne à répéter. Par exemple, la séquence "CBCBCBCB" peut être compressée en "[4CB]" ou de manière récursive en "[2[2CB]]". L'objectif est de restituer la chaîne originale en applqiuant une décompression récursive.

Entrée : Une seule ligne contenant la chaîne cryptée, composée uniquement de chiffres, de lettres majuscules, et des caractères '[' et ']'.

Sortie : Une ligne affichant la chaîne décompressée.

Exemple :

Entrée : AC[3FUN]
Sortie : ACFUNFUNFUN

Contraintes : Pour 50% des cas, la longueur de la chaîne décompressée ne dépasse pas 1000 caractères avec au maximum trois niveaux de comprestion. Pour 100% des cas, la longueur est jusqu'à 20000 caractères avec jusqu'à dix niveaux de compression.

Approche algorithmique : La solution utilise la récursion pour gérer les niveaux de compression. L'idée est de parcourir la chaîne d'entrée caractère par caractère. Lorsqu'un '[' est rencontré, on lit le nombre D, puis on appelle récursivement la fonction de décompression pour traiter la sous-chaîne X jusqu'au ']' correspondant. Le résultat récursif est répété D fois et ajouté au résultat courant. Les caractères hors compression sont directement ajoutés.

Points clés : Il est crucial de ne pas s'enlacer dans les détails des niveaux de compression imbriqués. En confiant la décompression des sous-chaînes à des appels récursifs, on simplifie la logique et on évite une complexité excessive.

Implémentation en C++ :

#include <iostream>
#include <string>
#include <cctype>
using namespace std;

string decompress(const string& input, int& pos) {
    string output;
    while (pos < input.length()) {
        char current = input[pos];
        if (current == '[') {
            pos++;
            int count = 0;
            while (pos < input.length() && isdigit(input[pos])) {
                count = count * 10 + (input[pos] - '0');
                pos++;
            }
            string segment = decompress(input, pos);
            for (int i = 0; i < count; i++) {
                output += segment;
            }
        } else if (current == ']') {
            pos++;
            return output;
        } else {
            output += current;
            pos++;
        }
    }
    return output;
}

int main() {
    string encrypted;
    getline(cin, encrypted);
    int index = 0;
    cout << decompress(encrypted, index);
    return 0;
}