Частотный анализ — разбор задачи

1. Идея

Нужно восстановить соответствие между буквами шифротекста и буквами открытого текста по частотам.

Дан эталонный порядок из 26 букв: order[0] — самая частая буква языка, order[1] — вторая по частоте и так далее.

Для шифротекста надо:

1. посчитать, сколько раз встречается каждая заглавная буква;
2. отсортировать все 26 букв:
   • сначала по убыванию частоты,
   • при равенстве частот — по алфавиту;
3. считать, что первая буква в этом порядке расшифровывается в order[0], вторая — в order[1] и так далее;
4. заменить все заглавные буквы в тексте по найденному соответствию.

Пробелы и любые другие не-буквы менять не нужно.

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

Наблюдение 1

Даже если какая-то буква вообще не встретилась в тексте, она всё равно участвует в сортировке.

То есть мы сортируем не только буквы, которые есть в сообщении, а все 26 заглавных букв от A до Z.

Наблюдение 2

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

Например, если A, C и D встретились по 0 раз, то среди них порядок будет A, C, D.

Наблюдение 3

После сортировки удобно построить массив decode, где:

• decode[0] — во что превращается буква A,
• decode[1] — во что превращается буква B,
• ...
• decode[25] — во что превращается буква Z.

Тогда расшифровка каждого символа делается за O(1).

3. Алгоритм

1. Считать строку order.
2. Считать строку text.
3. Создать массив cnt из 26 чисел, заполненный нулями.
4. Пройти по строке text:
   • если символ — заглавная латинская буква, увеличить её счётчик.
5. Создать список всех букв от A до Z.
6. Отсортировать этот список:
   • по убыванию cnt,
   • при равенстве — по самой букве.
7. Построить массив decode:
   • если на i-м месте после сортировки стоит буква letters[i], то она должна перейти в order[i].
8. Ещё раз пройти по тексту:
   • если символ — заглавная буква, заменить её через decode;
   • иначе оставить как есть.
9. Вывести полученную строку.

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

Пусть после подсчёта частот мы получили точный порядок букв шифротекста по правилам задачи:

• чаще встречающиеся идут раньше;
• при равной частоте раньше идёт буква с меньшим алфавитным номером.

Именно такой порядок и требуется сопоставить с данным эталонным порядком букв открытого текста.

Значит:

• самая частая буква шифротекста должна соответствовать order[0],
• вторая по частоте — order[1],
• ...
• последняя — order[25].

После этого каждая заглавная буква шифротекста получает ровно одну расшифровку. Массив decode как раз хранит это соответствие.

Когда мы заменяем в исходном тексте каждую заглавную букву на decode[...], мы выполняем ровно ту подстановку, которую требует условие. Все остальные символы не меняются, что тоже совпадает с условием.

Следовательно, алгоритм выдаёт правильный расшифрованный текст.

5. Сложность

Подсчёт частот занимает O(n), где n — длина текста.

Сортировка 26 букв занимает O(26 log 26), то есть это просто константа.

Построение ответа снова занимает O(n).

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

Память:

• массив частот на 26 элементов,
• массив соответствия на 26 элементов,
• ответ длины n.

Итого: O(n) по памяти, если хранить итоговую строку, или O(1) дополнительной памяти без учёта ответа.

6. Код на C++17

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

using namespace std;

int main() {
    string order;
    string text;

    getline(cin, order);
    getline(cin, text);

    vector<int> cnt(26, 0);
    for (char c : text) {
        if ('A' <= c && c <= 'Z') {
            cnt[c - 'A']++;
        }
    }

    vector<char> letters;
    for (char c = 'A'; c <= 'Z'; c++) {
        letters.push_back(c);
    }

    sort(letters.begin(), letters.end(), [&](char a, char b) {
        int ca = cnt[a - 'A'];
        int cb = cnt[b - 'A'];
        if (ca != cb) return ca > cb;
        return a < b;
    });

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

    string result = text;
    for (int i = 0; i < (int)result.size(); i++) {
        char c = result[i];
        if ('A' <= c && c <= 'Z') {
            result[i] = decode[c - 'A'];
        }
    }

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

7. Код на Python 3

order = input()
text = input()

cnt = [0] * 26
for c in text:
    if 'A' <= c <= 'Z':
        cnt[ord(c) - ord('A')] += 1

letters = [chr(ord('A') + i) for i in range(26)]
letters.sort(key=lambda c: (-cnt[ord(c) - ord('A')], c))

decode = [''] * 26
for i in range(26):
    decode[ord(letters[i]) - ord('A')] = order[i]

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

print(''.join(result))