CS
Задачник Базовый курс EN

Задача

CRC по строкам

предподсчёт хеширование битовые трюки

Контрольную сумму CRC считают так. Состояние c — 32-битное число, сначала все единицы, FFFFFFFF. Для каждого байта b данных: c = c XOR b, и затем восемь раз: если младший бит c равен единице, c = (c >> 1) XOR P, иначе c = c >> 1. В конце результат — c XOR FFFFFFFF. Число P задаёт вариант CRC: для CRC-32 из zip и PNG это EDB88320, для CRC-32C из iSCSI и файловых систем — 82F63B78.

Посчитайте CRC каждой строки входа, байтов её записи в UTF-8 без перевода строки.

Вход

В первой строке P — восемь шестнадцатеричных цифр. Во второй — число строк q. Дальше q строк текста, возможно пустых. Всех байтов строк вместе — не больше 2,5·10⁶.

Выход

Для каждой строки — её CRC восемью шестнадцатеричными цифрами строчными буквами.

Примеры

Пример 1

Вход
EDB88320
4
Война и мир
War and Peace
War and peace
123456789
Выход
5d1bede8
d9b331de
18721eda
cbf43926

Ограничения

Время · Python
1000 мс
Время · Go
1000 мс
Память
256 МБ
Проверка
6 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Восемь шагов на байт зависят только от одного числа — младшего байта состояния после XOR с байтом данных. Сколько разных значений у этого числа?

2Идея

Двести пятьдесят шесть. Посчитаем заранее, во что восемь шагов превращают каждое из них: T[i] — восемь сдвигов, начиная с числа i. Тогда байт обрабатывается одним шагом: c = (c >> 8) XOR T[(c XOR b) & FF]. Таблица — 256 чисел, килобайт памяти, строится один раз за 2048 шагов.

3Разбор

Почему это верно. Восемь шагов делают с состоянием две вещи: старшие 24 бита просто уезжают на 8 позиций вправо, а младшие 8 бит решают, какие копии P будут вычтены через XOR. Вычитания зависят только от младшего байта, и всё, что они делают, — XOR с одним и тем же числом, которое и записано в T. Сдвиг и XOR можно переставить, поэтому восемь шагов равны одному: сдвиг на байт и XOR с записью таблицы.

Решение по битам верно, но делает восемь шагов цикла на каждый байт. В Python это восемь раз дороже, и на тестах с текстом «Войны и мира» оно не укладывается в ограничение. В жизни CRC-32 считают готовыми функциями — zlib.crc32 в Python и hash/crc32 в Go, — а они используют ещё большие таблицы или особые команды процессора; как растёт скорость с размером таблицы и где она перестаёт расти, показывает статья «Предподсчёт и таблицы». Пятый тест считает CRC-32C, которого в стандартной библиотеке Python нет.

Проверить себя удобно на строке «123456789»: её CRC-32 — cbf43926, а CRC-32C — e3069283. Эти «проверочные значения» приводят в описании каждого варианта CRC.

3+Решение
4Сложность

O(256 · 8) на таблицу и O(1) на байт: всего O(суммы длин строк).

5Типичные ошибки
  • Без таблицы. Верно, но восемь шагов на байт — четвёртый тест.
  • Буквы, а не байты. CRC считается по байтам UTF-8: русская буква — два байта.
  • Пустая строка. Её CRC — 00000000: начальные единицы снимаются итоговым XOR.
  • Ведущие нули. CRC печатается всегда восемью цифрами.

Алгоритмы задачи

TEC Приём Предподсчёт и таблицы Посчитать ответы заранее и брать из таблицы: CRC-32 байтом за шаг вместо бита и где таблица перестаёт помогать. O(размер таблицы) один раз, затем O(1) на запрос 1 задача TEC Приём Битовые трюки Число как набор флажков: маски, младшая единица, подсчёт единиц и перебор подмножеств без рекурсии. O(1) на операцию над словом 1 задача
Каталог алгоритмов