Massima sottosequenza comune
Problem
Date due sequenze, devi trovare la lunghezza della loro sottosequenza comune più lunga.
Input
La prima riga dell'input contiene il numero N – la lunghezza della prima sequenza (1 ≤ N ≤ 1000). La seconda riga contiene i membri della prima sequenza (separati da uno spazio) – numeri interi non superiori a 10000 modulo.
La terza riga contiene il numero M – la lunghezza della seconda sequenza (1 ≤ M ≤ 1000). La quarta riga contiene i membri della seconda sequenza (separati da uno spazio) – numeri interi non superiori a 10000 modulo.
Uscita
Obbligatorio per produrre un singolo numero – lunghezza la massima sottosequenza comune delle due sequenze date, o 0 se non esiste tale sottosequenza.
| Input |
Uscita |
|
3
1 2 3
3
2 3 1
|
2 |