Solved by 1005 users: ...
UserDateAttemptTimeCMSC
armagedec`14 mar 2015`C++100.02107
sb3ar`13 mar 2008`Ruby911.00160
vitekkk`11 mar 2005`FPC1?.??163
sb3ar`13 mar 2008`Ruby710.35164
bush`02 mar 2006`FPC400.27165
VArt`03 feb 2008`C++1200.07166
VArt`03 feb 2008`C++1300.07166
sb3ar`13 mar 2008`Ruby610.31167
VArt`03 feb 2008`C++1100.07169
VArt`03 feb 2008`C++900.07171
VArt`03 feb 2008`C++800.07173
mishko-007`20 jan 2013`Perl205.10182
sb3ar`09 mar 2008`Ruby507.74182
bmicky`14 mar 2009`C++400.25185
Tulegenov_Amir`23 jan 2007`Kylix100.31185
Belthazor`18 apr 2012`Python1806.76185
Mikolka.by`06 dec 2007`FPC400.02188
 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 DevGroupThe page was generated in 210ms