Description

Given two sequences s1 and s2 (of any type). Find their longest common subsequence(s) (LCS). For example, let s1 = {3, 6, 5, 7, 7, 1, 4, 8} and s2 = {4, 45, 7, 7, 1, 9, 3, 6}. Their LCS is {7, 7, 1} of length 3. Implement this function as a template that works on any class T, and call your function template with int. The I/O format is as follows.

• Input an integer indicating the length of the sequence.
• Each element of a sequence is separated by a whitespace.
• The user first inputs two sequences. Then s/he inputs a mode as follows.
  • If mode is len then your program should only output the length of the LCS.
  • If mode is seq then your program should output all LCSs. If there are more than one, then your program should output them in lexicographic order.

Sample Input1

14
343 5 3 434 1 2 3 4 5 6 7 8 9 10
13
9 2348 32 5 1 2 3 4 5 6 88 9934 0
len

Sample Output1

6

Sample Input2

14
343 5 3 434 1 2 3 4 5 6 7 8 9 10
13
9 2348 32 5 1 2 3 4 5 6 88 9934 0
str

Sample Output2

1 2 3 4 5 6

Sample Input3

10
18 3 1 4 7 7 5 3 9 6
11
8 78 5 3 9 2 9 1 4 7 10
str

Sample Output3

1 4 7
5 3 9

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss