Die größte allgemeine Untersequenz
Problem
Es gibt zwei Sequenzen, es ist erforderlich, die Länge ihrer größten gemeinsamen Untersequenz zu ermitteln.
Eingabe
Die erste Zeile der Eingabe enthält die Zahl N – die Länge der ersten Sequenz (1 ≤ N ≤ 1000). Die zweite Zeile enthält die Elemente der ersten Sequenz (durch ein Leerzeichen) – ganze Zahlen, die modulo nicht größer als 10000 sind.
Die dritte Zeile enthält die Zahl M – Länge der zweiten Sequenz (1 ≤ M ≤ 1000). In der vierten Zeile werden die Mitglieder der zweiten Sequenz (durch ein Leerzeichen) – Ganzzahlen angegeben, die modulo nicht größer als 10000 sind.
Ausgabe
Es ist erforderlich, eine einzelne Zahl – die Länge der größten gemeinsamen Untersequenz zweier dieser Sequenzen auszugeben, oder 0, wenn es keine solche Untersequenz gibt.
| Eingabe |
Ausgabe |
|
3
1 2 3
3
2 3 1
|
2 |