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

Задача

Похожие пароли

похожесть дедупликация безопасность предподсчёт хеш-таблица

Сервис не хочет разрешать пароли, похожие на утёкшие: если запрещён password, то password1 ничем не лучше. Чтобы понять, насколько списки утечек полны вариаций, нужно посчитать в них пары похожих паролей.

Сходство паролей меряют по триграммам — подстрокам из трёх символов подряд. Множество триграмм пароля — все его подстроки длины 3, каждая один раз. Сходство двух паролей — коэффициент Жаккара их множеств: |A ∩ B| / |A ∪ B|. Посчитайте, сколько пар паролей из списка имеют сходство не меньше T/100. Среди тестов — 10 000 самых частых паролей из открытого списка SecLists.

Вход

В первой строке — число паролей n и порог T (1 ≤ n ≤ 4·104, 50 ≤ T ≤ 100). Дальше n различных паролей, по одному в строке: от 4 до 30 печатных символов ASCII без пробелов.

Выход

Одно число — сколько неупорядоченных пар паролей имеют сходство не меньше T/100.

Во втором примере abab, baba и ababab — разные пароли с одним и тем же множеством триграмм {aba, bab}, у aaaa и aaaaaa множество {aaa}: четыре пары со сходством 1.

Примеры

Пример 1

Вход
7 60
password
password1
passw0rd
drowssap
123456
1234567
qwerty
Выход
2

Пример 2

Вход
5 50
abab
baba
ababab
aaaa
aaaaaa
Выход
4

Ограничения

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

Разбор

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

1Подсказка 1

Если у пароля из пяти триграмм сходство с другим не меньше 0,6, сколько триграмм у них общих как минимум? А может ли среди первых трёх триграмм пароля — в любом заранее выбранном порядке — не оказаться ни одной общей?

2Подсказка 2

Выберите порядок, в котором первыми идут самые редкие триграммы. Тогда списки «у каких паролей эта триграмма среди первых» будут короткими.

3Идея

Если J(A, B) ≥ t, то |A ∩ B| ≥ t·|A ∪ B| ≥ t·|A|, то есть общих элементов не меньше ⌈t·|A|⌉. Запишем все множества в одном общем порядке. Тогда среди первых |A| − ⌈t·|A|⌉ + 1 элементов A есть общий: иначе все общие уместились бы в последние ⌈t·|A|⌉ − 1 мест. Самый ранний общий элемент лежит в этих «префиксах» и у A, и у B. Значит, кандидаты — только пары, чьи префиксы пересекаются, а их даёт инвертированный индекс по префиксам. Это префиксный фильтр из статьи.

4Разбор

Посчитаем, в скольких паролях встречается каждая триграмма, и упорядочим триграммы от редких к частым. Пароли обрабатываем по возрастанию числа триграмм: тогда у каждого уже обработанного партнёра множество не больше. Для очередного пароля s проходим его префикс; по индексу находим пароли, у которых та же триграмма в префиксе, и каждый проверяем один раз. Сначала фильтр размера: J ≤ |o| / |s|, и если |o| < t·|s|, пару можно не считать. Затем точное пересечение. После этого кладём префикс s в индекс. Всё сравнение — в целых: 100·|A ∩ B| ≥ T·|A ∪ B|, без деления.

На 10 000 паролях с порогом 0,6 пар 50 005 000, а точных проверок — 62 762, в восемьсот раз меньше. Похожих пар 4484: password и password1, 123456 и 1234567. На 35 516 паролях из слов «Войны и мира» с порогом 0,7 — 574 019 проверок вместо 630 миллионов пар.

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

Подсчёт и сортировка триграмм — O(L + G log G), где L — суммарная длина паролей, G — число разных триграмм. Дальше — сумма длин просмотренных списков индекса плюс точные проверки кандидатов. В худшем случае, когда все пароли состоят из одних и тех же частых триграмм, это снова O(n²), но на настоящих списках кандидатов в сотни раз меньше, чем пар.

6Типичные ошибки
  • Все пары. Ответ верный, но 5·107 пар — уже много для Python, а 6·108 — для любого языка.
  • Триграммы списком. Повторы считаются один раз: у ababab две триграммы, а не четыре.
  • Сравнение в дробях. Сходство, ровно равное порогу, должно считаться; деление в числах с плавающей точкой может его потерять.
  • Префикс не той длины. Нужно |A| − ⌈t·|A|⌉ + 1 элементов; на один короче — и пары, у которых общий элемент последний в префиксе, теряются.
  • Частые триграммы впереди. Ответ тот же, но в префиксах окажутся 123 и ass с длинными списками: на паролях из романа проверок станет 18 миллионов вместо 574 тысяч — в тридцать раз больше.

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

SYS Алгоритм MinHash и LSH Подпись из K минимумов хешей: доля совпавших — оценка сходства Жаккара; полосы LSH сводят похожие пары в одни корзины. O(K·S) на подписи, O(n·b) на корзины, плюс проверка кандидатов 2 задачи SYS Структура данных Инвертированный индекс и BM25 Словарь «слово → документы, где оно есть»: запрос читает несколько коротких списков вместо всех текстов. O(сумма длин списков слов запроса); «И» галопом — O(m·log(n/m)) 2 задачи
Каталог алгоритмов