B) Поднимем грамотность
Не буду описывать все решение, но пусть мы построили два бора - один для всех слов, а другой для всех слов с обратным порядком букв. Пусть мы находимся в некоторой вершине первого бора, как мы можем продолжить это слово? E) Давайте попутешествуем.
В задаче требуется найти не более 1000 первых лексикографически упорядоченных наибольших общих подпоследовательностей для двух данных строк. Во-первых, в условии была неточность - в конце было написано "найдите все кратчайшие маршруты". Должно быть "Найдите все такие маршруты". Надеюсь, никого это не смутило, т.к. из предыдущего предложения должно было быть понятно, что же все-таки требуется найти. Во-вторых, строки можно строить рекурсивно, пытаясь сначала найти наименьшую совпадающую пару букв, потом следующую за ней и т.д. Строчки можно складывать в set и потом выводить. Я не совсем уверен в корректности этого решения (хоть оно и зашло у меня на spoj.pl), поэтому перепроверю все на свежую голову.
М. Окунев |
| |||||||||