supersglzc/lcs_ass

dynamic programming: Longest Common Subsequence

Longest Common Subsequence

Dynamic Programming

Part I. Longest Common Subsequence of Two Sequences

Compute the length of a longest common subsequence of two sequences 𝐴 = (𝑎₁, 𝑎₂, . . . , 𝑎_n) and 𝐵 = (𝑏₁, 𝑏₂, . . . , 𝑏_m), defined as the largest non-negative integer 𝑝 such that there exist indices 1 ≤ 𝑖₁ < 𝑖₂ < · · · < 𝑖_p ≤ 𝑛 and 1 ≤ 𝑗₁ < 𝑗₂ < · · · < 𝑗_p ≤ 𝑚, such that 𝑎_i1 = 𝑏_j1 , . . . , 𝑎_ip = 𝑏_jp .

Input: two sequences 𝐴 and 𝐵 of lengths n and m respectively.

Output: the length p of their longest common subsequence

Input format

First line: 𝑛. 
Second line: 𝑎1, 𝑎2, . . . , 𝑎𝑛. 
Third line: 𝑚. 
Fourth line: 𝑏1, 𝑏2, . . . , 𝑏𝑚. 
Constraints. 1 ≤ 𝑛, 𝑚 ≤ 100; −29 < 𝑎𝑖, 𝑏𝑖 < 29.

Output Format

Output 𝑝.

Example 1

Input:
3
2 7 5
2
2 5
Output:
2

A common subsequence of length 2 is (2, 5).

Example 2

Input:
1
7
4
1 2 3 4
Output:
0

The two sequences do not share elements.

Example 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).

Implement the solution to the LCP2 problem in file lcp2.c.

Part II. Longest Common Subsequence of Three Sequences

Given three sequences 𝐴 = (𝑎₁, 𝑎₂, . . . , 𝑎_n), 𝐵 = (b₁, b₂, . . . , b_m), and 𝐶 = (c₁, c₂, . . . , c_l), find the length of their longest common subsequence, i.e., the largest non-negative integer 𝑝 such that there exist indices 1 ≤ 𝑖₁ < 𝑖₂ < · · · < 𝑖_p ≤ 𝑛, 1 ≤ 𝑗₁ < 𝑗₂ < · · · < 𝑗_p ≤ 𝑚, 1 ≤ 𝑘₁ < 𝑘₂ < · · · < 𝑘_p ≤ 𝑙 such that 𝑎_i1 = 𝑏_j1 = 𝑐_k1 , . . . , 𝑎_ip = 𝑏_jp = 𝑐_kp.

The input and output formats are the same as for the previous problem.

Example 1

Input:
3
1 2 3
3
2 1 3
3
1 3 5
Output:
2

A common subsequence of length 2 is (1, 3).

Example 1

Input:
5
8 3 2 1 7
7
8 2 1 3 8 10 7
6
6 8 3 1 4 7
Output:
3

One common subsequence of length 3 in this case is (8, 3, 7). Another one is (8, 1, 7).

Implement the solution to the LCP3 problem in file lcp3.c.