Длиннейшая общая подпара

Будем называть пару строк (α, β) подпарой строки γ, если γ = γ₁αγ₂βγ₃ для некоторых (возможно пустых) строк γ₁, γ₂ и γ₃. Длиной пары строк будем называть сумму длин составляющих ее строк: |(α, β)| = |α| + |β|.

По заданным двум строкам ξ и η найдите их длиннейшую общую подпару, то есть такую пару строк (α, β), что она является подпарой как ξ, так и η, и ее длина максимальна.

Входные данные

Входной файл INPUT.TXT содержит две непустые строки ξ и η, состоящие из маленьких букв английского алфавита. Длина каждой из строк не превышает 2000.

Выходные данные

В выходной файл OUTPUT.TXT выведите α на первой строке выходного файла и β на второй строке.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]