Три редакции
Абзац учебника правили дважды: сначала стиль, потом факты. Редактору интересно, что пережило обе правки, — какие слова остались на своих местах во всех трёх редакциях. Слова можно выбрасывать из любой редакции, но порядок оставшихся менять нельзя: нужна самая длинная последовательность слов, которая читается в каждой из трёх редакций, если пропустить лишнее.
Слово — кусок между пробелами, со всеми знаками препинания: «текста,» и «текста» — разные слова. Во втором примере и в одном из скрытых тестов — настоящий абзац курса этого сайта в трёх редакциях.
Вход
Три строки — три редакции, от старой к новой. В каждой от 1 до 120 слов, разделённых одиночными пробелами.
Выход
В первой строке — наибольшее число слов k. Во второй — сами слова через пробел (пустая строка, если k = 0). Если вариантов несколько, выведите любой.
Примеры
Пример 1
зима весна лето лето зима весна лето осень
1 лето
Пример 2
4 июля 1997 года посадочный аппарат Mars Pathfinder сел в долине Арес на Марсе и выпустил на грунт маленький вездеход «Соджорнер». Через несколько дней, вскоре после того как аппарат начал собирать метеорологические данные, его компьютер стал перезагружаться целиком. Каждый сброс стоил части собранных данных, а повторялись сбросы снова и снова. 4 июля 1997 года посадочный аппарат Mars Pathfinder сел в долине Арес на Марсе и выпустил на грунт маленький вездеход «Соджорнер». Через несколько дней, вскоре после того как аппарат начал собирать метеорологические данные, его компьютер стал перезагружаться целиком. Сбросы повторялись, и каждый стоил части собранных данных. 4 июля 1997 года посадочный аппарат Mars Pathfinder сел в долине Арес на Марсе и выпустил на грунт маленький вездеход «Соджорнер». В первые же дни, вскоре после того как аппарат начал собирать метеорологические данные, его компьютер стал перезагружаться целиком. Сбросы повторялись, и каждый обрывал программу работ, заданную с Земли на этот день.
36 4 июля 1997 года посадочный аппарат Mars Pathfinder сел в долине Арес на Марсе и выпустил на грунт маленький вездеход «Соджорнер». вскоре после того как аппарат начал собирать метеорологические данные, его компьютер стал перезагружаться целиком. и
Ограничения
- Время · Python
- 3000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Первая мысль: найти общее у первых двух редакций, а потом общее у результата и третьей. Проверьте её на первом примере: зима, весна, лето.
2Подсказка 2
У двух строк таблица двумерная: клетка — пара «сколько слов взято из первой, сколько из второй». Что должна помнить клетка, если строк три?
3Идея
Наибольших общих подпоследовательностей у двух редакций может быть много, а склейка «сначала две, потом третья» берёт одну из них и может выбрать неудачную: в первом примере у «зима весна лето» и «лето зима весна» общая часть одна — «зима весна», и третья редакция с ней не делит ни слова, хотя «лето» есть во всех трёх. Поэтому считаем сразу по трём: T[i][j][k] — длина наибольшей общей подпоследовательности первых i, j и k слов. Если последние слова всех трёх начал равны, T = 1 + T[i − 1][j − 1][k − 1]; иначе — наибольшее из трёх клеток, где одно из начал короче на слово.
4Разбор
Доказательство то же, что для двух строк. Посмотрим на последние слова трёх начал. Если все три равны, лучший ответ можно считать кончающимся этим словом во всех трёх: иначе его последнее слово можно заменить на него. Если не все равны, хотя бы одно из трёх последних слов не стоит в конце ответа, и его можно выбросить — останется задача с одним началом короче.
Таблица из 121³ ≈ 1,8 миллиона клеток. В Python удобно хранить её плоским списком и считать индекс i · S + j · W + k, где W = r + 1 и S = (q + 1)(r + 1), — так быстрее, чем список списков списков. Сами слова восстанавливаются путём назад из дальнего угла: если три слова равны и клетка получена по диагонали — слово в ответ и шаг по диагонали; иначе шаг в ту соседнюю клетку, где то же число.
Во втором примере — настоящий абзац о Mars Pathfinder в трёх редакциях. Склейка двух ответов теряет там одно слово: 35 вместо 36.
4+Решение
5Сложность
O(p · q · r) времени и памяти. Для k строк таблица k-мерная и растёт как nk; Дэвид Майер в 1978 году показал, что для произвольного числа строк задача NP-трудна, так что для многих строк быстрого точного алгоритма не ждут.
6Типичные ошибки
- LCS(LCS(a, b), c). Не проходит первый пример: из многих общих частей двух редакций берётся одна, и не обязательно та, что подходит третьей.
- Попарные длины. Наименьшая из трёх попарных длин — только оценка сверху: общая часть всех трёх может быть короче.
- Слова без знаков препинания. По условию «текста,» и «текста» — разные слова; сравнивайте куски между пробелами как есть.