<PREV Problem:
NEXT>
Solved by 1001 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

LCS problem

Time limit = 2 second(s)

You are given two sequences of latin letters X = {x1,x2,x3, .. ,xm} and Y = {y1,y2,y3, .. ,yn}, ( 1 ≤ m, n ≤ 1000).

Your task is to find letter sequence Z which is subseqence of X and Y and has maximum length.

Definition
A is subsequence of B if we can drop some elements from B and get A.

Input. Two lines with X and Y.

Output. One line with Z. If there are many solutions then output any. If there is no common subsequence then output "Empty".

Input#1
BDCABA
ABCBDAB
Output#1
BCBA
Input#2
ABCD
EFGH
Output#2
Empty
Input#3
LEKVA
EKVAL
Output#3
EKVA

Author:
The problem of Longest Common Subsequence (LCS-problem),
Tests and description by Giorgi Lekveishvili.
15 April 2004

<PREV | Problem set | Search related messages | NEXT>


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

SW soft NIX
ID = 23.20.13.165