1. Идея

Нужно обратить процесс столбцовой перестановки.

При шифровании:

• исходный текст записали в таблицу по строкам;
• затем столбцы отсортировали по буквам ключа;
• после этого выписали столбцы сверху вниз в новом порядке.

Значит, при расшифровке надо сделать обратное:

• понять, в каком порядке столбцы шли при шифровании;
• разрезать шифротекст на равные части, каждая часть — это один столбец;
• поставить каждый столбец обратно на его исходное место;
• прочитать таблицу по строкам.

Так как длина шифротекста кратна длине ключа, все столбцы имеют одинаковую высоту, и задача упрощается.

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

Наблюдение 1. Сколько строк в таблице

Пусть:

• m — длина ключа, то есть число столбцов;
• n — длина шифротекста.

Тогда число строк равно rows = n / m.

Это корректно, потому что по условию n кратно m.

Наблюдение 2. Как узнать порядок столбцов

Для каждого столбца важны:

• буква ключа в этом столбце;
• исходный индекс столбца.

Например, для ключа BA получаем пары:

• (B, 0)
• (A, 1)

После сортировки получится:

• (A, 1)
• (B, 0)

Это значит, что при шифровании сначала выписали столбец 1, потом столбец 0.

Наблюдение 3. Что делать с одинаковыми буквами

По условию, если буквы ключа одинаковы, раньше идёт столбец, который левее.

Если хранить пары (буква, индекс) и просто отсортировать их, именно это и получится:

• сначала сравниваются буквы;
• если буквы равны, сравниваются индексы.

То есть одинаковые буквы автоматически упорядочатся слева направо.

Наблюдение 4. Как восстановить столбцы

Шифротекст состоит из подряд записанных столбцов в отсортированном порядке.

Значит, если в таблице rows строк, то каждый столбец занимает ровно rows символов.

Нужно пройти по столбцам в отсортированном порядке и каждой такой части шифротекста вернуть её в столбец с исходным индексом.

3. Алгоритм

1. Считать key и cipher.
2. Вычислить:
   • m = len(key) — число столбцов,
   • n = len(cipher) — длина шифротекста,
   • rows = n / m — число строк.
3. Построить массив пар (key[i], i) для всех столбцов.
4. Отсортировать этот массив.
   • Теперь элементы идут в том порядке, в котором столбцы выписывались в шифротекст.
5. Создать массив cols из m строк.
   • cols[c] будет содержать весь c-й исходный столбец.
6. Идти по отсортированному массиву и по очереди брать из cipher куски длины rows.
   • Если очередной элемент сортировки указывает на исходный столбец original_index, то соответствующий кусок записываем в cols[original_index].
7. После этого все столбцы стоят на своих местах.
8. Восстановить исходный текст:
   • для каждой строки r от 0 до rows - 1
   • для каждого столбца c от 0 до m - 1
   • добавить символ cols[c][r].
9. Вывести результат.

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

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

Пусть исходный текст был записан в таблицу с rows строками и m столбцами.

Обозначим исходные столбцы как 0, 1, 2, ..., m - 1.

При шифровании:

1. Столбцы упорядочиваются по ключу. Это полностью определяется сортировкой пар (key[i], i), потому что:
   • сначала столбцы сравниваются по букве ключа;
   • при равных буквах левый столбец должен идти раньше, то есть меньший индекс раньше.
2. Затем столбцы выписываются сверху вниз в этом порядке. Значит, шифротекст состоит из подряд идущих блоков длины rows, где каждый блок — содержимое одного столбца.

Теперь посмотрим на расшифровку.

• Мы строим тот же самый отсортированный порядок столбцов.
• Берём шифротекст по блокам длины rows.
• Каждый блок ставим в тот исходный столбец, который указан в отсортированной паре.

Значит, после этого для каждого исходного индекса c строка cols[c] содержит ровно тот столбец, который был в таблице до перестановки.

Остаётся только прочитать таблицу по строкам:

• в строке r стоят символы cols[0][r], cols[1][r], ..., cols[m-1][r].

Именно так исходный текст и был записан в таблицу до шифрования. Следовательно, полученная строка совпадает с исходным текстом.

Значит, алгоритм корректен.

5. Сложность

Пусть:

• m — длина ключа;
• n — длина шифротекста.

Тогда:

• сортировка m пар занимает O(m log m);
• разрезание шифротекста и восстановление столбцов занимает O(n);
• чтение таблицы по строкам тоже занимает O(n).

Итоговая сложность: O(n + m log m).

По памяти:

• храним порядок столбцов и сами столбцы,
• суммарно это O(n + m).

6. Код на C++17

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

using namespace std;

int main() {
    string key, cipher;
    cin >> key >> cipher;

    int m = (int)key.size();
    int n = (int)cipher.size();
    int rows = n / m;

    vector<pair<char, int>> order;
    for (int i = 0; i < m; i++) {
        order.push_back({key[i], i});
    }

    sort(order.begin(), order.end());

    vector<string> cols(m);
    int pos = 0;
    for (int i = 0; i < m; i++) {
        int original_index = order[i].second;
        cols[original_index] = cipher.substr(pos, rows);
        pos += rows;
    }

    string result;
    result.reserve(n);
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < m; c++) {
            result += cols[c][r];
        }
    }

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

7. Код на Python 3

key = input().strip()
cipher = input().strip()

m = len(key)
n = len(cipher)
rows = n // m

order = []
for i in range(m):
    order.append((key[i], i))

order.sort()

cols = [""] * m
pos = 0
for ch, original_index in order:
    cols[original_index] = cipher[pos:pos + rows]
    pos += rows

result = []
for r in range(rows):
    for c in range(m):
        result.append(cols[c][r])

print("".join(result))