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

Соседи пароля

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

Сервис проверяет новые пароли: не лежит ли пароль в нескольких правках от частого. Правка — вставка, удаление или замена одного символа. Словарь — частые пароли по убыванию частоты, первый самый частый. Для каждого запроса найдите, сколько паролей словаря лежат от него не дальше чем в k правках, и самый частый из них.

Тесты с третьего по шестой — 10 000 самых частых паролей из открытого списка SecLists, а запросы — частые пароли с опечатками и случайные строки.

Вход

В первой строке n (1 ≤ n ≤ 10⁴), дальше n разных паролей по одному в строке. Затем число запросов q (1 ≤ q ≤ 300) и q строк: пароль и k (0 ≤ k ≤ 2), причём запросов с k = 2 не больше двадцати. Пароли — от 1 до 20 печатных символов ASCII без пробелов.

Выход

Для каждого запроса — число паролей словаря не дальше k правок и самый частый из них, через пробел. Если таких нет — 0 -.

Примеры

Пример 1

Вход

6
password
123456
qwerty
passw0rd
qwerty1
dragon
5
qwerty 0
qwerty 1
pasword 1
pasword 2
monkey 2

Выход

1 qwerty
2 qwerty
1 password
2 password
0 -

Пример 2

Вход

5
abc
abd
xbc
abcd
zzz
4
abc 1
ab 1
zz 0
bcd 2

Выход

4 abc
2 abc
0 -
4 abc

Ограничения

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

Разбор

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

1Подсказка 1

Сравнить запрос с каждым паролем — 3 · 10⁶ таблиц расстояния редактирования на тест. Можно ли, сравнив запрос с одним паролем x, сразу сказать про многие другие, что они далеко?

2Подсказка 2

Если d(q, x) = 9, а d(x, w) = 4, то по неравенству треугольника d(q, w) ≥ 5. Заранее разложите пароли по расстоянию до одного из них — и так рекурсивно.

3Идея

BK-дерево. Узел — пароль, ребро к ребёнку помечено расстоянием между ними. Для запроса в пределах k: на узле с расстоянием d спускаемся только по рёбрам e из [d − k, d + k] — в остальных поддеревьях все пароли дальше k.

4Разбор

Вставляем пароли по порядку частоты: первый — корень, каждый следующий спускается по ребру своего расстояния, пока не найдёт свободное место. Номер узла совпадает с номером пароля, поэтому самый частый из найденных — с наименьшим номером. Обход — своим стеком: глубина дерева из 10 000 паролей — 26.

При одной правке есть и другой путь: перебрать все строки в одной правке от запроса — их около (2L + 1) · 95 — и искать каждую в хеш-таблице. При двух правках вариантов уже сотни тысяч, а дерево обходит пятую часть словаря; поэтому таких запросов в тестах немного.

4+Решение

5Сложность

Построение — около глубины сравнений на пароль. Запрос с одной правкой на этом словаре сравнивает в среднем несколько процентов паролей, с двумя — около пятой части; оценки лучше перебора в худшем случае у BK-дерева нет.

6Типичные ошибки

Сравнивать со всеми. Это wrong.py: 300 запросов на 10 000 паролей — три миллиона таблиц, и в третьем тесте времени уже не хватает.
Окно с одной стороны. Если отбрасывать только рёбра больше d + k, ответ останется верным, но дерево обойдёт много лишнего: рёбра меньше d − k тоже не нужны.
Самый частый — не первый найденный. Обход идёт не по порядку номеров; минимум номера надо считать отдельно.
Рекурсия на дереве глубиной 26 проходит, но при неудачном порядке вставки — например, по алфавиту — дерево бывает гораздо глубже.

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

STR Структура данных BK-дерево Все пароли в одной-двух правках от данного: неравенство треугольника отрезает целые ветви — и где оно перестаёт помогать. O(N · глубина) на построение 1 задача STR Алгоритм Редакционное расстояние Наименьшее число вставок, удалений и замен между двумя строками — таблица m × n и выравнивание по ней. O(m · n) 2 задачи