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

Задача

Старые блоки в новом файле

хеширование скользящее окно потоковая обработка сравнение версий в проде

У получателя лежит старая версия файла, у отправителя — новая. Получатель режет старую версию на блоки по B байт: блок номер 0 — байты с 0-го по (B − 1)-й, блок 1 — следующие B байт, и так далее; последний блок может быть короче. Отправитель идёт по новой версии слева направо, начиная с позиции i = 0, и на каждом шаге смотрит на кусок новой версии с позиции i длиной L = min(B, сколько байт осталось до конца):

  • если этот кусок в точности совпадает с каким-нибудь блоком старой версии — той же длины и байт в байт, — отправитель сообщает номер блока и переходит к позиции i + L;
  • иначе он отправляет байт на позиции i как есть и переходит к i + 1.

Посчитайте, сколько блоков будет найдено, сколько байт уйдёт как есть и на сколько непрерывных кусков эти байты разобьются (кусок — байты, отправленные подряд, без найденного блока между ними). Три теста — настоящие правки главы базового курса этого сайта; переводы строк в них заменены пробелами.

Вход

В первой строке — размер блока B. Во второй — старая версия, в третьей — новая: последовательности байтов длиной от 1 до 400 000, без байтов перевода строки (10) и возврата каретки (13). 1 ≤ B ≤ 400 000.

Выход

Три числа через пробел: число найденных блоков, число байт, отправленных как есть, и число кусков, на которые они разбились.

В первом примере старая версия режется на блоки «the », «quic», «k br», …, «azy », «dog». В новой перед «the» вставлено «so », и все блоки сдвинулись на три байта, но отправитель находит их на новом месте; в конце «cat» вместо «dog» — три байта. Во втором примере блок «abc» встречается в старой версии дважды, а короткий последний блок «ab» совпадает с концом новой версии.

Примеры

Пример 1

Вход
4
the quick brown fox jumps over the lazy dog
so the quick brown fox jumps over the lazy cat
Выход
10 6 2

Пример 2

Вход
3
abcabcab
xabcab
Выход
2 1 1

Ограничения

Время · Python
6000 мс
Время · Go
1500 мс
Память
256 МБ
Проверка
10 тестов

Разбор

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

1Подсказка 1

Проверить, есть ли кусок среди блоков, легко: положите блоки старой версии в хеш-таблицу по их содержимому. Но для этого кусок надо вырезать и захешировать — L байт на каждой позиции. Сколько это стоит, если совпадений нет, а блоки по двести тысяч байт?

2Идея

При шаге на один байт кусок меняется на два байта: один уходит слева, другой приходит справа. Нужна сумма, которую можно так же сдвигать за O(1). Слабая сумма rsync из статьи — a = Σx и b = Σ(L − k)·xk по модулю 216 — сдвигается двумя формулами: a ← a − xушёл + xпришёл, b ← b − L·xушёл + a. Подойдёт и полиномиальный хеш из статьи о скользящем хеше. Сумма служит фильтром: кусок вырезают и сравнивают с блоками только тогда, когда его сумма совпала с суммой какого-нибудь блока.

3Разбор

Сначала проходим по старой версии: каждый блок кладём в хеш-таблицу по содержимому, а его пару (a, b) — в множество. Потом идём по новой версии. Сумму куска на позиции i считаем заново, только когда она «свежая» — в начале и после найденного блока; дальше катим её. Если пара сумм есть в множестве, вырезаем кусок и ищем его в таблице: нашли — блок, прыгаем на L; нет — это ложная тревога, и байт уходит как есть.

Конец файла требует аккуратности. Когда до конца меньше B байт, кусок при сдвиге не только теряет байт слева, но и ничего не получает справа: L уменьшается на единицу. Формулы для этого случая — a ← a − x, b ← b − L·x: у уходящего байта вес был L, у остальных веса не меняются. Так короткий последний блок старой версии находится в самом конце новой — и только там: кусок длиной меньше B бывает лишь у конца файла (тесты 7–9).

На правке описания главы (третий тест) находится 139 блоков из 140: одна правка в начале сдвинула всё остальное на сто с лишним байт, но блоки нашлись на новых местах, и как есть ушло 598 байт.

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

O(|старая| + |новая|) на суммы и их сдвиг, плюс вырезание куска на каждую совпавшую сумму. Настоящие совпадения стоят в сумме O(|новая|) — каждый найденный блок съедает свои байты. Ложные тревоги на 32 битах сумм случаются редко: в статье на правке главы их нет ни одной.

5Типичные ошибки
  • Искать блоки только на границах. Если после промаха прыгать сразу на B байт или сравнивать блоки с одинаковых позиций, одна вставка в начале прячет все блоки после неё. Так ошибается уже первый пример.
  • Вырезать кусок на каждой позиции. Ответ верный, но это O(|новая|·B): на шестом тесте — около шестидесяти миллиардов байт.
  • Окно у конца файла. Если считать, что кусок всегда длиной B, короткий последний блок не найдётся никогда, а суммы у конца станут неверными.
  • Отрицательный остаток. В Go и C остаток от деления отрицательного числа отрицателен: после вычитания приведите сумму обратно в [0, 216).

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

SYS Алгоритм Алгоритм rsync Передаёт только изменённые куски файла: суммы блоков туда, новые байты обратно; блоки находятся на любом смещении. O(n + m): сумма окна сдвигается за O(1), сильная сумма — только при совпадении слабой 2 задачи STR Приём Полиномиальный хеш Хеш любого куска строки за O(1) из хешей начал: сравнение подстрок, окна, общие начала — с оценкой вероятности ошибки. O(n) подготовка, O(1) хеш куска 2 задачи
Каталог алгоритмов