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 (1≤D≤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 (1 ≤ n ≤ 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 (1 ≤ m ≤ 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

---

ukryj komentarze

2011-10-09 16:28:56 Piotr Kąkol @f4ntasy - Ty się rąbnąłeś i przykład jest poprawny. Czemu myślisz, że jest błędny?

2011-10-09 16:18:52 f4ntasy Hmmm... ja sie rąbnąłem, czy w skład danych testowych wchodzi powyższy(błędny zresztą) przykład?

2011-02-08 23: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

2011-02-08 22:51:57 Marcin Lach Podsłowo musi mieć jakiś logiczny sens czy to ma być po prostu jakiś losowo posklejany ciąg liter? Jeśli to może być losowy ciąg, to stokrotka i deskorolka mają 7 wspólnych liter, więc długość najdłuższego podsłowa powinna być równa 7.

2010-10-21 00:20:30 Ewa Piotrowska A to nie powinno być w łatwych?

2009-05-29 13:09:52 Piotr Chamera Dlaczego nie można rozwiązać tego w lispie?