Fișierul intrare/ieșire cmlsc.in, cmlsc.out Sursă Infoarena
Autor teorie Adăugată de avatar Marcela Marcela Marcela
Timp de execuție pe test 0.1 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in cmlsc.out
5 3
1 7 3 9 8
7 5 8
2
7 8

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 1 categorii