Description

Given two sequences s$1$ and s$2($of any type$).$ Find their longest common subsequence$($s$)($LCS$).$ For example, let s$1=\{3,6,5,7,7,1,4,8\}$ and s$2=\{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 Input$1$

$14$

$3435343412345678910$

$13$

$923483251234568899340$

len

Sample Output$1$

$6$

Sample Input$2$

$14$

$3435343412345678910$

$13$

$923483251234568899340$

str

Sample Output$2$

$123456$

Sample Input$3$

$10$

$18314775396$

$11$

$8785392914710$

str

Sample Output$3$

$147$

$539$