-
Notifications
You must be signed in to change notification settings - Fork 8
Description
Problem Introduction
Compute the length of a longest common subsequence of two sequences.
Problem Description
Task.
Given 2 sequences A = (A1, ..., An) and B = (B1, ..., Bm),
find the length of their longest common subsequence,
i.e., the largest non-negative integer p such that there exist indices 1 ≤ i1 < ··· < ip ≤ n and 1 ≤ j1 < ··· < jp ≤ m,
such that Ai1 = Bj1, ..., Aip = Bjp.
Input Format.
1st line: n.
2nd line: A1, A2, ..., An.
3rd line: m.
4th line: B1, B2, ..., Bm.
Constraints.
1 ≤ n, m ≤ 100;
−10^9 < Ai, Bi < 10^9
Output Format. Output p.
E.g. 1,
Input:
3
2 7 5
2
2 5
Output: 2
A common subsequence of length 2 is (2, 5).
E.g. 2,
Input:
1
7
4
1 2 3 4
Output: 0
The two sequences do not share elements.
E.g. 3,
Input:
4
2 7 8 3
4
5 2 8 7
Output: 2
One common subsequence is (2, 7).
Another one is (2, 8).