Module: Greatest common subsequence


Problem

1 /5


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
2 3 1
2