SPOJ Problem Set (partial)

452. Longest Common Subsequence

Problem code: TLCS

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

Added by:	Michał Małafiejski
Date:	2004-11-10
Time limit:	5s
Source limit:	50000B
Memory limit:	256MB
Cluster:	Pyramid (Intel Pentium III 733 MHz)
Languages:	All except: PERL 6

hide comments



2012-06-18 17:06:56 ~wil93 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
2012-06-18 17:06:56 Madhavan Is there a better approach than O(nm) ? I am always getting TLE for O(mn) computation and O(m+n) printing.
2012-06-18 17:06:56 DING Why I always got TLE, I use DP with top-down and bottom-up, all get TLE, frustrated...