Longest Common Subsequence
All submissions for this problem are available.
For a given two words x = x1x2...xn
and y = y1y2...ym
find the longest common subsequence, i.e. z = z1z2...zk
such that every two consecutive elements of z are equal to some two elements of x: xa, xb, and y: yc, yd where a < b and c < d. Assume, that elements of words are letters 'a' - 'z' and m,n <= 1000.
t [the number of test cases <= 1000]
case 1 Y [or N when no answer to this case]
d [the length of the lcs]
zj p q [position of zj in x and in y, respectively]
Input: 3 5 ddacc 3 cac 7 cbbccbc 4 aaca 4 cbeb 5 fdceb Output: case 1 Y 2 a 3 2 c 4 3 case 2 N case 3 Y 3 c 1 3 e 3 4 b 4 5 Score 2
|Time Limit:||2.02 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.