Два частотных словаря
«Войну и мир» разрезали пополам и для каждой половины выписали её слова от самого частого к самому редкому. Оставили только слова, которые попали в оба списка, так что списки состоят из одних и тех же слов, только в разном порядке. Насколько похожи два частотных словаря? Одна из мер — сколько слов можно оставить в обоих списках так, чтобы их порядок совпал.
Даны два списка из одних и тех же n различных слов. Найдите наибольшее число слов, которые идут в одном и том же порядке в обоих списках, — то есть длину наибольшей общей подпоследовательности двух списков.
Вход
В первой строке — n (1 ≤ n ≤ 100 000). Во второй — n различных слов первого списка, в третьей — те же n слов в порядке второго списка, через пробел. Слово — непустая строка из букв и цифр.
Выход
Одно число — наибольшее число слов, порядок которых в двух списках совпадает.
Примеры
Пример 1
6 и в не что он на и не в он что на
4
Пример 2
4 князь пьер наташа андрей князь пьер наташа андрей
4
Ограничения
- Время · Python
- 3000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Это наибольшая общая подпоследовательность, но таблица n × n при n = 100 000 — десять миллиардов клеток. Чем эти два списка проще двух произвольных строк?
2Подсказка 2
Каждое слово встречается в каждом списке ровно один раз. Замените каждое слово первого списка его номером во втором. Что такое общая подпоследовательность на языке этих номеров?
3Идея
Выпишем для слов первого списка, по порядку, их места во втором. Набор слов идёт в одном порядке в обоих списках тогда и только тогда, когда в первом списке они идут слева направо, а их места во втором растут. Значит, ответ — длина наибольшей возрастающей подпоследовательности этих мест, и её находит лестница за O(n log n).
4Разбор
Словарь «слово → место во втором списке» строится одним проходом. Потом проходим первый список и для каждого слова кладём его место на лестницу: двоичный поиск первой ступеньки не меньше, замена или новая ступенька сверху. Ответ — число ступенек. Места все разные, поэтому строгость здесь не ловушка: bisect_left и bisect_right дают одно и то же.
На «Войне и мире»: из 403 слов, попавших в первую пятисотку обеих половин романа, в одном порядке идут 72; из 3210 слов первых пяти тысяч — 338; из 7442 слов, встретившихся хотя бы дважды в каждой половине, — 1259. Для сравнения, у случайного перемешивания ста тысяч слов в одном порядке остаётся всего 616 — около 2√n, как и предсказывает задача Улама. Частотные словари двух половин книги похожи куда больше, чем случайные.
Этот же приём лежит в основе алгоритма Ханта и Шиманского (1977) для общего случая: если пар одинаковых элементов в двух последовательностях немного, общую подпоследовательность ищут по ним, а не по всей таблице.
4+Решение
5Сложность
O(n log n) времени и O(n) памяти вместо O(n²) у таблицы.
6Типичные ошибки
- Таблица общей подпоследовательности. Верна, но квадратична: на тесте со ста тысячами слов не успевает.
- Сравнивать списки по позициям. Число слов, стоящих в обоих списках на одном и том же месте, — другая и куда более грубая мера: один лишний сдвиг в начале сбивает все места после него.
Алгоритмы задачи
O(m · n)
2 задачи
DP
Алгоритм
Наибольшая возрастающая подпоследовательность
Самая длинная растущая цепочка элементов в исходном порядке: пасьянс и двоичный поиск за n log n.
O(n log n)
2 задачи