TLCS - Longest Common Subsequence

no tags 

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.


N [the number of series <= 1000]
n x
m y


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]

Text grouped in [ ] does not appear in the input and output file.


5 ddacc
3 cac
7 cbbccbc
4 aaca
4 cbeb
5 fdceb

case 1 Y
a 3 2
c 4 3
case 2 N
case 3 Y
c 1 3
e 3 4
b 4 5


hide comments
neeru_priya: 2016-07-06 19:19:43

can anyone explain the test case 2 :( i am not able to understand why answer is case 2 N

shef: 2015-09-03 19:34:56

why is my solution giving 0 as the result even after half and hour of my submission.How can it stay in waiting for this long?

LEMONICE: 2015-05-29 20:06:09

this question has horrible test cases: you have to print the answers from top to bottom in order to get accepted. When I was printing it the other way around, I kept on getting a WA. eg. case 1:
c 3 1
c 4 3
is correct but
c 4 3
c 3 1 is not.
Also, even with exact same algo, I had to make some useless optimisations to get it accepted.

pandu ranga rao: 2014-12-30 11:54:36

Can any one explain why answer for Case 2 is N. I think the answer for Case 2 is

case 2 Y
c 7 3

ABHISHEK: 2014-10-31 01:15:12

Do we have to print N if length of lcs is <= 1?

wil93: 2014-10-31 01:15:12

TLE... I think we should consider the constraint of the values of characters (just from 'a'-'z' for a total of only 26 distinct chars)

I also found some documentation about this

Madhavan: 2014-10-31 01:15:12

Is there a better approach than O(nm) ?
I am always getting TLE for O(mn) computation and O(m+n) printing.

DING: 2014-10-31 01:15:12

Why I always got TLE, I use DP with top-down and bottom-up, all get TLE, frustrated...

Added by:mima
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)