Fişierul intrare/ieşire:cmlsc.in, cmlsc.outSursăInfoarena
AutorTeorieAdăugată deMarcelaMarcela Marcela
Timp execuţie pe test0.1 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Cel mai lung subşir comun

Fie v un vector cu N elemente. Se numeşte subşir de lungime K al vectorului v un nou vector v' = (vi1, vi2, ... viK), cu i1 < i2 < ... < iK. De exemplu, vectorul v = (5 7 8 9 1 6) conţine ca subşir şirurile (5 8 6) sau (7 8 1), dar nu conţine subşirul (1 5). Se dau doi vectori A şi B cu elemente numere naturale nenule.

Cerinţă

Să se determine subşirul de lungime maximă care apare atât în A cât şi în B.

Date de intrare

Fişierul de intrare cmlsc.in conţine pe prima linie M şi N, numărul de elemente pentru vectorul A, respectiv pentru B. A doua linie conţine M numere naturale, elementele vectorului A. A treia linie conţine descrierea vectorului B sub acelaşi format.

Date de ieşire

Fişierul de ieşire cmlsc.out va conţine pe prima linie MAX, lungimea maximă a unui subşir comun. A doua linie va conţine MAX numere ce reprezintă un subşir comun de lungime maximă pentru A si B. Dacă există mai multe soluţii se poate afişa oricare.

Restricţii

  • 1 ≤ M, N ≤ 1024
  • Numerele din cei doi vectori nu depăşesc 256

Exemplu

cmlsc.incmlsc.out
5 3
1 7 3 9 8
7 5 8
2
7 8
Trebuie sa te autentifici pentru a trimite solutii. Click aici