Решение задачи "Декомпрессия текста" с Codeforces

Без пояснения   Просмотров: 12


Дана строка, состоящая из букв латинского алфавита. В целях ее компрессии разрешается любые ее непустые подстроки (подстрокой называется последовательность идущих подряд символов строки) сжимать по следующему правилу. Строка A, состоящая из повторений некоторой непустой строки B, записывается как символ «(», затем количество повторений (целое число от 1 до 105, записанное без ведущих нулей), затем строка B, и, наконец, символ «)». Например, строку ababab можно сжать, записав ее как (3ab).

В данной задаче допускается повторное сжатие подстрок строки. Разумеется, можно сжимать лишь части, состоящие только из букв латинского алфавита. Например, строку acacacaacacaca можно сжать, записав ее в виде (2acacaca), и осуществить дальнейшую компрессию: (2(3ac)a).

Ваша задача осуществить обратное преобразование, то есть преобразовать строку из сжатого вида в несжатый.

Код

#include <bits/stdc++.h>

using namespace std;

int main()
{
    string n;
    cin >> n;
    int close = n.find(')');
    if(close < 0)
        cout << n;
    else{
        int open = n.rfind('(', close);
        while(open + 1){
            int chb = n.find_first_of("123456789", open);
            int chl = n.find_last_of("123456789", close);
            string s = n.substr(chb, chl - chb + 1);
            int res = 0, temp = 1;
            while(s.size()){
                res+=(s[s.size() - 1] - 48) * temp;
                temp*=10;
                s.erase(s.size() - 1);
            }
            string r;
            string t = n.substr(chl + 1, close - chl - 1);
            for(int i = 0; i < res; ++i)
                r+=t;
            n.replace(open, close - open + 1,  r);
            close = n.find(')');
            open = n.rfind('(', close);


        }
        cout << n;
    }
    return 0;
}
    // (2A)
    //(2    (3Ac(3AC)(2BB)(1C)N )   )
    //(2    (3AcACACACBBBBCN )   )
    //AcACACACBBBBCNAcACACACBBBBCNAcACACACBBBBCNAcACACACBBBBCNAcACACACBBBBCNAcACACACBBBBCN

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться