Longest Common Subsequence (längste gemeinsame Teilfolge)
Sie haben zwei Sequenzen,
a und b, mit den Längen n und m. Ihre Aufgabe ist es, die Länge der längsten gemeinsamen Teilsequenz dieser beiden Sequenzen zu ermitteln.💡
Eine Teilsequenz ist eine neue Sequenz, die entsteht, indem einige (oder keine) Elemente aus der ursprünglichen Sequenz entfernt werden, ohne die Reihenfolge der verbleibenden Elemente zu verändern.
Eingabe
Die erste Zeile der Eingabe enthält zwei durch Leerzeichen getrennte ganze Zahlen
n und m (1 ≤ n, m ≤ 1000).
Die zweite Zeile enthält n durch Leerzeichen getrennte ganze Zahlen , welche die Elemente der Sequenz a darstellen (1 ≤ ≤ ).
Die dritte Zeile enthält m durch Leerzeichen getrennte ganze Zahlen , welche die Elemente der Sequenz b darstellen (1 ≤ ≤ ).Ausgabe
Geben Sie eine einzelne ganze Zahl aus – die Länge der längsten gemeinsamen Teilsequenz von
a und b.Beispiele
Eingabe | Ausgabe |
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