Laiko ribojimas: 1s

Atminties ribojimas: 16MB

Jei norite pateikti savo sprendimą - prisijunkite.

Ilgiausias bendras posekis

Duotos dvi skaičių sekos. Parašykite programą, kuri rastų ilgiausią posekį, bendrą abiems duotoms sekoms.

Formaliai: duotos skaičių sekos a_1,a_2,...,a_n ir b_1,b_2,...,b_m. Parašykite programą, kuri rastų seką c_1,c_2,...,c_k, tokią, kad:

  • seką C būtų galima gauti iš sekos A, išbraukiant kai kuriuos jo narius,
  • seką C būtų galima gauti iš sekos B, išbraukiant kai kuriuos jo narius,
  • sekos C ilgis (k) būtų maksimalus.

Pradiniai duomenys

Pirmoje pradinių duomenų eilutėje įrašytas sekos A ilgis n, o antroje eilutėje įrašyti sekos A nariai: a_1,a_2,...,a_n (1\\lea_i\\len). Kitose dvejose eilutėse tokiu pačiu formatu įrašyta seka B. Sekų ilgiai neviršija 1000.

Rezultatai

Pirmoje rezultatų failo eilutėje turi būti įrašyta seka C: pirmoje eilutėje sekos ilgis k, o antroje - sekos C nariai (k sveikųjų skaičių).

Pavyzdys

Pradiniai duomenys Rezultatai 
6
6 5 4 3 2 1 
6
1 6 2 5 3 4
 
3
6 5 3