|
Длиннейшая общая подпара
(Время: 2 сек. Память: 64 Мб Сложность: 48%)
Будем называть пару строк (α, β) подпарой строки γ, если γ = γ1αγ2βγ3 для некоторых (возможно пустых) строк γ1, γ2 и γ3. Длиной пары строк будем называть сумму длин составляющих ее строк: |(α, β)| = |α| + |β|.
По заданным двум строкам ξ и η найдите их длиннейшую общую подпару, то есть такую пару строк (α, β), что она является подпарой как ξ, так и η, и ее длина максимальна.
Входные данные
Входной файл INPUT.TXT содержит две непустые строки ξ и η, состоящие из маленьких букв английского алфавита. Длина каждой из строк не превышает 2000.
Выходные данные
В выходной файл OUTPUT.TXT выведите α на первой строке выходного файла и β на второй строке. Если существует несколько решений, выведите любое из них.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | abacabadabacaba
acabacadacabaca | acaba
abaca |
| 2 | ab
bc | b
|
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
