Разбор задачи «Шифр Виженера»

1. Идея

Нужно обработать строку text по ключу key в одном из двух режимов:

• E — шифрование;
• D — расшифровка.

Каждая буква текста сдвигается на величину, заданную соответствующей буквой ключа:

• a означает сдвиг 0,
• b — 1,
• ...
• z — 25.

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

Значит, задача сводится к простому проходу по строке слева направо с отдельным счётчиком позиции в ключе.

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

Наблюдение 1. Ключ удобно перевести в массив сдвигов

Вместо букв ключа удобно сразу хранить числа:

• для символа c сдвиг равен c - 'a'.

Например, для ключа bad получим массив:

• b -> 1
• a -> 0
• d -> 3

То есть [1, 0, 3].

Наблюдение 2. Маленькие и большие буквы надо обрабатывать отдельно

Для строчных букв диапазон — от 'a' до 'z'.

Для заглавных — от 'A' до 'Z'.

Сдвигать их нужно одинаково, но относительно разных начал алфавита:

• для строчной буквы базой будет 'a',
• для заглавной — 'A'.

Это позволяет сохранить регистр.

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

Если символ не является буквой английского алфавита, то:

• он просто копируется в ответ;
• позиция в ключе не увеличивается.

Это особенно важно для пробелов, запятых, цифр и других символов.

Наблюдение 4. Шифрование и расшифровка отличаются только знаком

Если буква текста имеет номер x от 0 до 25, а сдвиг равен shift, то:

• при шифровании: x = (x + shift) % 26
• при расшифровке: x = (x - shift + 26) % 26

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

3. Алгоритм

1. Считываем mode, key и text.
2. Преобразуем ключ в массив чисел shifts.
3. Создаём пустой ответ.
4. Заводим счётчик pos — сколько букв текста уже обработано. По нему определяем, какой символ ключа использовать:
   • индекс в ключе равен pos % len(key).
5. Идём по всем символам строки text:
   • если это строчная буква:
     • берём нужный сдвиг;
     • переводим букву в число от 0 до 25;
     • прибавляем или вычитаем сдвиг в зависимости от режима;
     • превращаем число обратно в букву;
     • добавляем в ответ;
     • увеличиваем pos;
   • если это заглавная буква:
     • делаем то же самое, но с базой 'A';
     • увеличиваем pos;
   • иначе:
     • просто добавляем символ в ответ без изменений.
6. Выводим полученную строку.

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

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

Рассмотрим любой символ текста.

Случай 1. Это не английская буква

По условию такие символы:

• не изменяются;
• не учитываются при продвижении по ключу.

Алгоритм именно так и делает: копирует символ в ответ и не меняет pos.

Случай 2. Это строчная английская буква

Алгоритм берёт текущий символ ключа по номеру pos % m, где m — длина ключа. Это соответствует циклическому повторению ключа.

Далее буква переводится в число от 0 до 25, к нему:

• либо прибавляется сдвиг при шифровании,
• либо вычитается при расшифровке.

После этого результат берётся по модулю 26, поэтому переходы через конец алфавита обрабатываются правильно.

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

После обработки буквы pos увеличивается на 1, то есть ключ сдвигается на следующий символ, как и требуется.

Случай 3. Это заглавная английская буква

Полностью аналогично предыдущему случаю, только работа идёт в алфавите от 'A' до 'Z'. Поэтому регистр сохраняется.

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

5. Сложность

Пусть длина текста равна n, а длина ключа равна m.

• Преобразование ключа: O(m)
• Обработка текста: O(n)

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

Память:

• массив сдвигов ключа: O(m)
• строка ответа: O(n)

Итоговая дополнительная память: O(n + m).

6. Код на C++17

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

using namespace std;

int main() {
    string mode, key, text;
    cin >> mode;
    cin >> key;
    cin.ignore();
    getline(cin, text);

    vector<int> shifts;
    for (char c : key) {
        shifts.push_back(c - 'a');
    }

    string result;
    result.reserve(text.size());

    int m = (int)key.size();
    int pos = 0;

    for (char c : text) {
        if (c >= 'a' && c <= 'z') {
            int shift = shifts[pos % m];
            int x = c - 'a';
            if (mode == "E") {
                x = (x + shift) % 26;
            } else {
                x = (x - shift + 26) % 26;
            }
            result.push_back(char('a' + x));
            pos++;
        } else if (c >= 'A' && c <= 'Z') {
            int shift = shifts[pos % m];
            int x = c - 'A';
            if (mode == "E") {
                x = (x + shift) % 26;
            } else {
                x = (x - shift + 26) % 26;
            }
            result.push_back(char('A' + x));
            pos++;
        } else {
            result.push_back(c);
        }
    }

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

7. Код на Python 3

mode = input().strip()
key = input().strip()
text = input()

shifts = [ord(c) - ord('a') for c in key]
m = len(key)
pos = 0
result = []

for c in text:
    if 'a' <= c <= 'z':
        shift = shifts[pos % m]
        x = ord(c) - ord('a')
        if mode == 'E':
            x = (x + shift) % 26
        else:
            x = (x - shift) % 26
        result.append(chr(ord('a') + x))
        pos += 1
    elif 'A' <= c <= 'Z':
        shift = shifts[pos % m]
        x = ord(c) - ord('A')
        if mode == 'E':
            x = (x + shift) % 26
        else:
            x = (x - shift) % 26
        result.append(chr(ord('A') + x))
        pos += 1
    else:
        result.append(c)

print(''.join(result))