TLCS - Longest Common Subsequence

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.

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]
zj p q [position of zj 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


Dodane przez:mima
Data dodania:2004-11-10
Limit czasu wykonania programu:5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU

ukryj komentarze
2014-12-21 15:29:02 Pawe³ Lampe
W angielskiej wersji "case 1 Y [or N when no answer to this case]" powinno być "case 1 Y [or N when you don't want to print answer to this case]"
2013-01-12 01:10:28 Piotr KÄ…kol
Podpowiedź: short int. Wiem, wiem.
2012-11-04 08:15:23 Mateusz Kap³on
To jest LCS i sądzę, że sprawdzarka nie jest aż tak głupia ;)
2010-09-23 09:50:02 Mieszko Kamyczek
A co jeżeli program w przypadku:
5 ddacc
3 cac
Wypisałby:
c 4 1
c 5 3
zamiast:
a 3 2
c 4 3

Przecież to także jest najdłuższy wspólny podciąg.

Ostatnio edytowany: 2010-09-23 09:50:16
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.