Programming contests

ECN programozó csapatverseny, 2017. május 13.

May 13, 2017 10:10 AM – May 13, 2017 3:10 PM

Longest Common Subsequence

Let X = (x1x2, …, xn) be a sequence. A sequence S = (s1s2, …, sk) is a subsequence of X if there exist the integers 0 < i1 < i2 < … < ik ≤ n such that sj = xij for j = 1, 2, …, k. For example: 2, 5, 7, 3 is a subsequence of 2, 9, 5, 7, 8, 1, 3, 4.

Given three sequences of integers: X = (x1x2, …, xm), Y = (y1y2, …, yn), and Z = (z1z2, …, zk), find the longest common subsequence. For example, for the sequences X = (2, 9, 5, 7, 8), Y = (9, 3, 5, 8), Z = (1, 9, 4, 5, 8), the longest common subsequence is (9, 5, 8).

Input Specification

The first line of the input contains the number of test cases. For each test case, there are four lines: The first line of them contains m, n, and k, the numbers of integers in each sequence, separated by a space (1 ≤ m, n, k ≤ 100). Each of the next three lines contains the elements (integer numbers) of a sequence, separated by a space. The sequence elements are integers from the interval [–32768, 32767].

Output Specification

For each test case, print in a line the elements of the longest common subsequence, separated by a space. If there is no solution, print the text “No solution”.

Sample Input

  1. 2
  2. 5 4 5
  3. 2 9 5 7 8
  4. 9 3 5 8
  5. 1 9 4 5 8
  6. 4 5 3
  7. 1 2 3 4
  8. 4 3 1 2 0
  9. 7 8 9
download as text file

Output for Sample Input

  1. 9 5 8
  2. No solution
download as text file
University of Debrecen; Faculty of Informatics; v. 03/01/2019