TLCS  Longest Common Subsequence
Wersja polska  English version 
For a given two words x = x1x2...x_{n} and y = y1y2...y_{m} find the longest common subsequence, i.e. z = z1z2...z_{k} such that every two consecutive elements of z are equal to some two elements of x: x_{a}, x_{b}, and y: y_{c}, y_{d} where a < b and c < d. Assume, that elements of words are letters 'a'  'z' and m,n <= 1000.
Input
N [the number of series <= 1000]
n x
m y
...
Output
case 1 Y [or N when no answer to this case]
d [the length of the lcs]
z_{j} p q [position of z_{j} in x and in y, respectively]
...
Text grouped in [ ] does not appear in the input and output file.
Example
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
hide comments
neeru_priya:
20160706 19:19:43
can anyone explain the test case 2 :( i am not able to understand why answer is case 2 N 

shef:
20150903 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:
20150529 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:


pandu ranga rao:
20141230 11:54:36
Can any one explain why answer for Case 2 is N. I think the answer for Case 2 is


ABHISHEK:
20141031 01:15:12
Do we have to print N if length of lcs is <= 1? 

wil93:
20141031 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)


Madhavan:
20141031 01:15:12
Is there a better approach than O(nm) ?


DING:
20141031 01:15:12
Why I always got TLE, I use DP with topdown and bottomup, all get TLE, frustrated... 
Added by:  mima 
Date:  20041110 
Time limit:  5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 