<ПРЕД Задача:
СЛЕД>
Задачу решили 1005 пользователей: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Задача LCS

Time limit = 2 секунд(ы)

Даны две последовательности латинских букв X = {x1,x2,x3, .. ,xm} и Y = {y1,y2,y3, .. ,yn}, ( 1 ≤ m, n ≤ 1000).

Задача --- найти их наибольшую общую подпоследовательность Z.

Определение
A является подпоследовательностью B если выкинув несколько элементов из B мы можем получить A.

Вход. Две строчки с X и Y.

Выход. Одна строчка с Z. Выведите одну из возможных строк Z если правильных ответов несколько. Если общей подпоследовательности нет, то выведите "Empty".

Вход#1
BDCABA
ABCBDAB
Выход#1
BCBA
Вход#2
ABCD
EFGH
Выход#2
Empty
Вход#3
LEKVA
EKVAL
Выход#3
EKVA

Автор:
Классическая задача про наибольшую общую подпоследовательность (LCS-problem),
Тесты и оисания Георгия Леквешвили.
15 Апреля 2004

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 35.172.233.215