Problem H: Subsequence Source file: subsequence.cpp This problem deals with find

Question

Problem H: Subsequence
Source file: subsequence.cpp
This problem deals with finding the longest common subsequence between a given set of
sequences. A subsequence of a given sequence is simply the given sequence with some
elements, possibly none, removed. For example, (2,4,1,5,7) is a subsequence of
(9,2,3,4,1,4,5,12,7,10,9). Every sequence is a subsequence of itself; the empty sequence is a
subsequence of every sequence. Given two sequences A and B, we say that X is a common
subsequence of A and B, if X is subsequence of both A and B. Given three sequences A, B,
and C, we say that X is a common subsequence of A, B and C, if X is a subsequence of A, is
a subsequence of B, and is a subsequence of C. The longest common subsequence of a given
trio of sequences is the maximum-length common subsequence of the three sequences.
Input
The user input will consist of several problem instances. Each line will include a single
integer, indicating the number of problem instances that will follow. Each problem instance
consists of three lines, each line consisting of a sequence of positive integers, separated by
space and terminated with a zero (the sequence will never contains zero and the final zero is
not considered part of the sequence). The length of the sequence will not be greater than 50.
Output
For each problem instance, your program should output a single line consisting of a single
integer, representing the length of the longest common subsequence of the three given
sequences. The common subsequence may contain duplicate numbers.
Sample Input
5
5 8 7 2 22 1 2 3 5 9 0
5 7 3 2 2 9 4 5 0
6 2 5 2 7 3 8 5 1 0
9 8 7 0
3 5 6 7 0
1 8 0
1 2 3 1 2 0
3 4 2 5 3 1 2 0
1 2 4 5 3 3 2 1 1 2 2 0
2 1 4 2 3 9 2 3 4 2 9 0
2 2 4 2 22 9 0
1 2 3 4 9 1 2 3 4 1 2 3 4 0
4 7 4 7 0
2 3 4 5 6 7 4 2 0
7 4 2 4 3 7 0
Sample Output
6
0
4
5
3

Explanation / Answer

// Compute the longest common subsequence between X and Y // On return, C will contain the LCS table. // C[m][n] will contain the length of the longest common subsequence. template size_t ** LCSLength(RanIt X, RanIt Xend, RanIt Y, RanIt Yend) { size_t m = std::distance(X, Xend); size_t n = std::distance(Y, Yend); size_t **C = Allocate2DArray(m+1, n+1); for (size_t i=0; i

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.