Given two sequences of characters, print the length of the longest common subsequence of both sequences. For example, the longest common subsequence of the following two sequences:
abcxyz dahcjyk
is acy of length 3.
The input of your program consist of pairs of lines where the first line is the first sequence of characters and the second line is the second sequence of characters. Each sequence is on a separate line and consists of at least 1 and at most 1,000 characters.
For each subsequent pair of input lines, output a line containing one integer number which satisfies the criteria stated above.
abcxyx dahcjyk
3
Modify the output so that in addition to printing the number, the longest common subsequence is printed following the number and one space. If the longest common subsequence is not unique, print any such longest common subsequence.
3 acy