Разбор задачи «Base64 в строку»

1. Идея

Нужно декодировать строку, записанную в формате Base64.

Base64 кодирует данные так:

• каждые 3 байта исходного текста превращаются в 4 символа;
• каждый символ Base64 кодирует 6 бит информации;
• если в конце исходных данных не хватило байтов, используются символы =.

Значит, задача решается блоками по 4 символа:

1. перевести каждый символ Base64 в число от 0 до 63;
2. собрать из этих четырёх значений одно 24-битное число;
3. извлечь из него исходные байты;
4. учесть символы = в конце блока.

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

Наблюдение 1. Алфавит Base64 фиксирован

Каждому символу соответствует своё значение:

• A-Z → 0..25
• a-z → 26..51
• 0-9 → 52..61
• + → 62
• / → 63

Поэтому удобно заранее построить таблицу соответствий.

Наблюдение 2. 4 символа Base64 = 24 бита

Каждый символ Base64 хранит 6 бит.

Значит, 4 символа дают:

• 4 * 6 = 24 бита

А это ровно:

• 3 * 8 = 24 бита,
• то есть 3 обычных байта.

Наблюдение 3. Как собрать число

Если значения четырёх символов равны a, b, c, d, то общий 24-битный блок равен:

x = (a << 18) | (b << 12) | (c << 6) | d

После этого можно извлечь байты:

• первый байт: (x >> 16) & 255
• второй байт: (x >> 8) & 255
• третий байт: x & 255

Наблюдение 4. Что делать с =

Символ = означает, что в конце данных не хватило байтов.

Возможны варианты:

• нет = → в блоке было 3 исходных байта;
• один = в конце → было 2 байта;
• два = в конце → был 1 байт.

В эталонном решении для удобства символы = временно заменяются на 0, а потом лишние байты просто не добавляются в ответ.

3. Алгоритм

1. Считать строку s.
2. Построить таблицу val, где для каждого символа Base64 хранится его числовое значение.
3. Завести пустую строку ответа.
4. Обрабатывать строку по 4 символа:
   • взять c1, c2, c3, c4;
   • получить их значения a, b, c, d;
   • если c3 == '=', то c = 0;
   • если c4 == '=', то d = 0;
   • собрать число x = (a << 18) | (b << 12) | (c << 6) | d;
   • добавить первый байт;
   • если c3 != '=', добавить второй байт;
   • если c4 != '=', добавить третий байт.
5. Вывести результат.

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

Base64 разбивает исходные данные на группы по 3 байта, то есть по 24 бита. Затем эти 24 бита делятся на 4 части по 6 бит, и каждая часть записывается одним символом из алфавита Base64.

При декодировании мы делаем обратную операцию:

1. каждый символ переводим обратно в его 6-битное значение;
2. склеиваем четыре 6-битных числа в один 24-битный блок;
3. разбиваем этот блок обратно на три 8-битных байта.

Если в конце есть символы =, это означает, что часть байтов в последнем блоке отсутствует. Тогда:

• при c3 == '=' реально существует только первый байт;
• при c4 == '=' реально существуют только первые два байта.

Именно поэтому в решении:

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

Так как вход гарантированно корректен, каждую группу из 4 символов можно безопасно декодировать именно таким способом.

5. Сложность

Пусть длина строки Base64 равна n.

• Время работы: O(n), потому что каждый символ обрабатывается один раз.
• Память: O(n) на строку ответа.

Дополнительная таблица символов имеет постоянный размер.

6. Код на C++17

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

using namespace std;

int main() {
    string s;
    cin >> s;

    vector<int> val(256, -1);
    for (int i = 0; i < 26; i++) val['A' + i] = i;
    for (int i = 0; i < 26; i++) val['a' + i] = 26 + i;
    for (int i = 0; i < 10; i++) val['0' + i] = 52 + i;
    val['+'] = 62;
    val['/'] = 63;

    string result;

    for (int i = 0; i < (int)s.size(); i += 4) {
        char c1 = s[i];
        char c2 = s[i + 1];
        char c3 = s[i + 2];
        char c4 = s[i + 3];

        int a = val[(unsigned char)c1];
        int b = val[(unsigned char)c2];
        int c = (c3 == '=') ? 0 : val[(unsigned char)c3];
        int d = (c4 == '=') ? 0 : val[(unsigned char)c4];

        int x = (a << 18) | (b << 12) | (c << 6) | d;

        result.push_back(char((x >> 16) & 255));
        if (c3 != '=') {
            result.push_back(char((x >> 8) & 255));
        }
        if (c4 != '=') {
            result.push_back(char(x & 255));
        }
    }

    cout << result;
    return 0;
}

7. Код на Python 3

s = input().strip()

val = {}
for i in range(26):
    val[chr(ord('A') + i)] = i
for i in range(26):
    val[chr(ord('a') + i)] = 26 + i
for i in range(10):
    val[chr(ord('0') + i)] = 52 + i
val['+'] = 62
val['/'] = 63

result = []

for i in range(0, len(s), 4):
    c1 = s[i]
    c2 = s[i + 1]
    c3 = s[i + 2]
    c4 = s[i + 3]

    a = val[c1]
    b = val[c2]
    c = 0 if c3 == '=' else val[c3]
    d = 0 if c4 == '=' else val[c4]

    x = (a << 18) | (b << 12) | (c << 6) | d

    result.append(chr((x >> 16) & 255))
    if c3 != '=':
        result.append(chr((x >> 8) & 255))
    if c4 != '=':
        result.append(chr(x & 255))

print(''.join(result))