TLCS - Longest Common Subsequence

no tags 

Dla podanych dwóch słów x = x1x2...xn and y = y1y2...ym wyznacz najdłuższy wspólny podciąg, to znaczy słowo z = z1z2...zk takie, że każde dwie kolejne litery z odpowiadają pewnym elementom z x: xa, xb oraz z y: yc, yd, gdzie a < b oraz c < d. Zakładać będziemy, że litery we wszystkich występujących słowach będą z zakresu 'a' - 'z' oraz m,n <= 1000.

Wejście

N [liczba zestawów testowych <= 1000]
n x
m y
...

Wyjście

case 1 Y [lub N gdy nie chcemy drukować odpowiedzi dla tego przypadku]
d [długość najdłuższego wspólnego podciągu]
zj p q [pozycja zj w x oraz w y]
...

Tekst w nawiasach [ ] nie występuje na wejściu ani nie powinien byc drukowany na wyjście.

Przykład

Wejście:
3
5 ddacc
3 cac
7 cbbccbc
4 aaca
4 cbeb
5 fdceb

Wyjście:
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

Wynik punktowy
2


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
1
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
Date:2004-11-10
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All