1. Идея

Дана таблица шифрования: для каждой буквы обычного алфавита известно, в какую букву она превращается.

Но требуется не зашифровать, а расшифровать текст. Значит, нужно построить обратное соответствие:

• если при шифровании A -> Q,
• то при расшифровке должно быть Q -> A.

После этого остаётся пройти по всему шифротексту:

• если символ — заглавная латинская буква, заменяем её по обратной таблице;
• если это не буква, оставляем как есть.

2. Наблюдения

1. Таблица замены — это перестановка из 26 заглавных букв.
   Значит, каждая буква встречается в ней ровно один раз, и обратная таблица тоже будет определена однозначно.

2. Прямая таблица говорит:

   • буква с индексом i в обычном алфавите переходит в cipher_alphabet[i].

3. Для расшифровки удобнее хранить именно обратную таблицу:

   • если cipher_alphabet[i] = X, то X должен расшифровываться в букву 'A' + i.

4. Пробелы и любые другие не-буквы менять не нужно.
   В условии шифротекст состоит из заглавных букв и пробелов, но проверка на диапазон 'A'..'Z' всё равно делает решение надёжным и понятным.

3. Алгоритм

1. Считать строку cipher_alphabet.
2. Считать строку text.
3. Создать массив rev размера 26, где:
   • rev[k] — это буква исходного текста, которая соответствует зашифрованной букве с индексом k.
4. Для каждого i от 0 до 25:
   • пусть cipher_alphabet[i] — буква, в которую шифруется 'A' + i;
   • тогда записываем:
     • rev[cipher_alphabet[i] - 'A'] = 'A' + i.
5. Пройти по всем символам строки text:
   • если символ — буква от A до Z, добавить в ответ rev[c - 'A'];
   • иначе добавить сам символ без изменений.
6. Вывести полученную строку.

4. Почему это работает

Докажем, что алгоритм действительно восстанавливает исходный текст.

Пусть некоторая исходная буква равна 'A' + i. По таблице шифрования она превращается в cipher_alphabet[i].

При построении массива rev мы записываем:

• для буквы cipher_alphabet[i] обратное значение равно 'A' + i.

Значит, если в шифротексте встречается буква cipher_alphabet[i], то при расшифровке мы получим ровно 'A' + i, то есть исходную букву.

Так работает для каждой из 26 букв, потому что таблица замены является перестановкой и все соответствия уникальны.

Для символов, которые не являются заглавными латинскими буквами, по условию нужно ничего не менять. Алгоритм именно так и делает.

Следовательно, каждая буква расшифровывается правильно, а остальные символы сохраняются. Значит, весь текст восстанавливается корректно.

5. Сложность

Построение обратной таблицы занимает O(26), то есть константное время.

Обработка текста длины n занимает O(n).

Итоговая сложность:

• по времени: O(n);
• по памяти: O(26) помимо ответа, то есть O(1).

6. Код на C++17

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

using namespace std;

int main() {
    string cipher_alphabet;
    string text;

    cin >> cipher_alphabet;
    cin.ignore();
    getline(cin, text);

    vector<char> rev(26);
    for (int i = 0; i < 26; i++) {
        rev[cipher_alphabet[i] - 'A'] = char('A' + i);
    }

    string result;
    for (char c : text) {
        if (c >= 'A' && c <= 'Z') {
            result += rev[c - 'A'];
        } else {
            result += c;
        }
    }

    cout << result << '\n';
    return 0;
}

7. Код на Python 3

cipher_alphabet = input()
text = input()

rev = [''] * 26
for i in range(26):
    rev[ord(cipher_alphabet[i]) - ord('A')] = chr(ord('A') + i)

result = []
for c in text:
    if 'A' <= c <= 'Z':
        result.append(rev[ord(c) - ord('A')])
    else:
        result.append(c)

print(''.join(result))