Greatest common subsequence
Problem
Given two sequences, you need to find the length of their longest common subsequence.
Input
The first line of the input contains the number N – the length of the first sequence (1 ≤ N ≤ 1000). The second line contains the members of the first sequence (separated by a space) – integers not exceeding 10000 modulo.
The third line contains the number M – the length of the second sequence (1 ≤ M ≤ 1000). The fourth line contains the members of the second sequence (separated by a space) – integers not exceeding 10000 modulo.
Output
Required to output a single number – length the greatest common subsequence of the two given sequences, or 0 if there is no such subsequence.
| Input |
Output |
|
3
1 2 3
3
2 3 1
|
2 |