Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

LENLCS - Długość najdłuższego wspólnego podciągu

Zadanie: Długość najdłuższego wspólnego podciągu (podsłowa)

Słowem u nazywamy dowolny skończony ciąg liter z alfabetu {a,b,c,...,z}. Podsłowem słowa u jest jego dowolny podciąg, np. podsłowami słowa deskorolka są między innymi ola, elka, deska, kolka, sroka. Dla danych dwóch słów u i v należy znaleźć długość ich najdłuższego wspólnego podsłowa.
Na przykład wspólne podsłowa słów u=deskorolka i v=stokrotka, to między innymi a, o, ka, kka, oa, sroka, sooka, skoka, skroka, soroka. Łatwo zauważyć że nie istnieje wspólne podsłowo słów u i v dłuższe niż 6 (długość podsłowa np. skroka). Tak więc w tym przykładzie długością maksymalnie długiego wspólnego podsłowa słow u i v jest liczba 6.

Zadanie
Napisz program, który:
  • wczyta ze standardowego wejścia: dwa słowa u i v,
  • znajdzie długość ich maksymalnie długiego wspólnego podsłowa,
  • wypisze wynik na standardowe wyjście.
Wejście
W pierwszej linii wejścia znajduje się jedna liczba całkowia D (1D≤10), oznaczjąca liczbę przypadków do rozważenia. Opis każdego przypadku podany jest w czterech wierszach. Pierwszy wiersz zawiera liczbę całkowitą n (1n ≤ 1 000), oznaczjąca długość słowa u. W następnym wierszu podane jest słowo u złozone wyłącznie z małych liter alfabetu angielskiego, tj. {a,b,...,z}. Trzeci wiersz zestawu zawiera liczbę całkowitą m (1m ≤ 1 000), oznaczjąca długość słowa v. W następnym wierszu podane jest słowo v złozone wyłącznie z małych liter alfabetu angielskiego.

Wyjście
Dla każdego przypadku z wejścia Twój program powinien wypisać (w osobnej linii dla każdego przypadku z wejścia) liczbę będącą długością maksymalnie długiego wspólnego podsłowa danych słów u i v.

Przykład
Dla danych wejściowych:
2
10
deskorolka
9
stokrotka
5
rafal
5
nowak
poprawną odpowiedzią jest:
6
1



Dodane przez:Rafal Nowak
Data dodania:2005-03-12
Limit czasu wykonania programu:0.694s
Limit długości kodu źródłowego5000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: BF CLPS LISP clisp LISP sbcl ERL GOSU HASK ICK JS-RHINO PHP PIKE PRLG-swi SCM guile SCM qobi WHITESPACE
Pochodzenie:Klasyka

ukryj komentarze
2011-02-08 22:08:12 Marcin Lach
wzięte z forum, żeby ułatwić takim jak ja:
<napisane przez: m_sasinowski>
poprawna odpowiedzia jest 6, a tym wspolnym podciagikem jest:
skroka

Wyjasnienie:

deskorolka
--sk-ro-ka

stokrotka
s--kro-ka
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.