Sottosequenza Comune Massima
Vi vengono fornite due sequenze,
a e b, di lunghezze rispettive n e m. Il vostro compito è trovare la lunghezza della massima sottosequenza comune a queste due sequenze.💡
Una sottosequenza è una nuova sequenza ottenuta eliminando alcuni (o nessuno) degli elementi dalla sequenza originale, senza modificare l’ordine di quelli che restano.
Dati in ingresso
La prima riga dell’input contiene due interi separati da spazio,
n e m (1 ≤ n, m ≤ 1000).
La seconda riga contiene n interi separati da spazio , che rappresentano gli elementi della sequenza a (1 ≤ ≤ ).
La terza riga contiene m interi separati da spazio , che rappresentano gli elementi della sequenza b (1 ≤ ≤ ).Dati in uscita
Stampate un unico intero: la lunghezza della massima sottosequenza comune tra
a e b.Esempi
Ingresso | Uscita |
5 4
2 1 5 3 4
2 5 1 4 | 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB