Пароль из утечки
Форма регистрации не принимает пароли из утечек. Вместо всего списка у неё есть фильтр Блума на m бит с k позициями на слово. Соберите фильтр из данного списка слов, ответьте на проверки и посчитайте, сколько раз фильтр ошибся.
Позиции слова вычисляются ровно так, как в статье:
- h — 64-битный хеш FNV-1a байтов слова: начальное значение 14695981039346656037; для каждого байта b по порядку h ← (h xor b) · 1099511628211 mod 2⁶⁴;
- h₁ — младшие 32 бита h, h₂ — старшие 32 бита h с установленным в 1 младшим битом;
- позиции — (h₁ + i · h₂) mod m для i = 0, 1, …, k − 1.
Вход
Первая строка: m и k (1 ≤ m ≤ 10⁷, 1 ≤ k ≤ 20). Вторая: число слов n (1 ≤ n ≤ 50 000). Третья: сами слова через пробел. Четвёртая: число проверок q (1 ≤ q ≤ 50 000). Пятая: проверяемые слова. Слова состоят из латинских букв, цифр и знаков без пробелов, длиной от 1 до 30 символов.
Выход
Для каждой проверки — maybe, если все её биты горят, или no. Последней строкой — сколько ответов maybe пришлось на слова, которых в списке не было.
Примеры
Пример 1
64 3 5 password qwerty dragon letmein monkey 6 dragon sunshine Qwerty 123456 letmein football
maybe no maybe no maybe no 1
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 7 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Сначала добейтесь, чтобы ваши позиции совпали с первым примером: dragon при m = 64, k = 3 даёт позиции 30, 1, 36. Если не совпадает — ошибка в хеше, а не в фильтре.
2Подсказка 2
Чтобы посчитать ложные срабатывания, нужно знать правду: было слово в списке или нет. Чем её быстро проверить?
3Идея
Фильтр — массив из m флагов. Вставка зажигает k позиций, проверка смотрит, горят ли все. Для подсчёта ошибок рядом держим обычное множество слов: ответ maybe на слово не из множества — ложное срабатывание. Множество здесь только для проверки фильтра; в настоящей форме регистрации его бы не было.
4Разбор
Читаем всё одним вызовом и работаем с байтами: в Python sys.stdin.buffer.read().split() даёт сразу bytes, и цикл по ним идёт по байтам — как раз то, что нужно FNV-1a. В Go удобно сканировать слова через bufio.Scanner с ScanWords.
Хеш считаем с маской 2⁶⁴ − 1 после каждого умножения: в Go переполнение uint64 делает это само, а в Python целые не переполняются, и маску нужно наложить явно. Потом режем хеш на две половины и получаем позиции.
Проверьте себя на крайнем случае m = 1: единственный бит зажигается первым же словом, и после этого фильтр отвечает maybe на всё. Формула из статьи здесь даёт 1 − e⁻¹ ≈ 0,63, а на деле ошибаемся всегда: формула приближённая и предполагает, что битов много.
4+Решение
5Сложность
Хеш слова длины L — O(L), позиции — O(k). Всего O((n + q)(L + k)) времени и m байт памяти (флаги можно сжать в биты, но при m ≤ 10⁷ и байты помещаются).
6Типичные ошибки
- Нет маски в Python. Хеш растёт до сотен бит, и позиции уходят в сторону. Решение проходит первый пример, если повезёт, и падает на остальных.
- Встроенный hash(). В Python он случайный при каждом запуске для строк — ответы будут меняться от запуска к запуску.
- Забыть «| 1» у h₂. Тогда при чётном h₂ часть позиций совпадёт, и биты будут не те.
- Медленный ввод. Сто тысяч слов через
input()по одному — лишние секунды.