magnify

Ilgiausias bendras posekis

Pradinių duomenų failas:
bendras.in  
Rezultatų failas:
bendras.out  
Laiko apribojimas:
1 s.  
Atminties apribojimas:
16 Mb.  

Užduotis

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

Antras bandymas: 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:

  1. seką C būtų galima gauti iš sekos A, išbraukiant kai kuriuos jo narius,
  2. seką C būtų galima gauti iš sekos B, išbraukiant kai kuriuos jo narius,
  3. 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_{i}\) – n sveikųjų skaičių (1 <= \(a_{i}\) <= n). 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
© Bronė Narkevičienė