Fișierul intrare/ieșire | cmlsc.in, cmlsc.out | Sursă | Infoarena |
---|---|---|---|
Autor | teorie | Adăugată de | Marcela • Marcela |
Timp de execuție pe test | 0.1 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
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 |