<PREV Problem:
NEXT>
Solved by 1005 users: ...
UserDateAttemptTimeCMSC
armagedec14 mar 2015C++100.02107 
sb3ar13 mar 2008Ruby911.00160 
vitekkk11 mar 2005FPC1?.??163 
sb3ar13 mar 2008Ruby710.35164 
bush02 mar 2006FPC400.27165 
VArt03 feb 2008C++1200.07166 
VArt03 feb 2008C++1300.07166 
sb3ar13 mar 2008Ruby610.31167 
VArt03 feb 2008C++1100.07169 
VArt03 feb 2008C++900.07171 
VArt03 feb 2008C++800.07173 
mishko-00720 jan 2013Perl205.10182 
sb3ar09 mar 2008Ruby507.74182 
bmicky14 mar 2009C++400.25185 
Tulegenov_Amir23 jan 2007Kylix100.31185 
Belthazor18 apr 2012Python1806.76185 
Mikolka.by06 dec 2007FPC400.02188 
Languages
C++
505
FPC
245
C
150
Java
64
Kylix
42
Python
7
Ruby
4
Lua
1
Perl
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

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 210ms

SW soft NIX
ID = 3.226.248.180