Comet OJ

C0543 [FJOI2016]所有公共子序列问题

内存限制：256 MB 时间限制：1000 ms

题目描述

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列 $X=x_1x_2\ldots x_m$，则另一序列 $Z=z_1z_2\ldots z_k$ 是 $X$ 的子序列是指存在一个严格递增下标序列 $i_1,i_2, \ldots ,i_k$ 使得对于所有 $j=1,2,…,k$ 有 $z_j=x_{i_j}$。

例如，序列 $Z=\texttt{GACT}$ 是序列 $X=\texttt{GCTACT}$ 的子序列，相应的递增下标序列为 $1,4,5,6$。给定两个序列 $X$ 和 $Y$，当另一序列 $Z$ 既是 $X$ 的子序列又是 $Y$ 的子序列时，称 $Z$ 是序列 $X$ 和 $Y$ 的公共子序列。例如，若 $X=\texttt{GCTACT}$，$Y=\texttt{GATCCT}$，序列 $\texttt{TT}$ 是 $X$ 和 $Y$ 的一个公共子序列，序列 $\texttt{GACT}$ 也是 $X$ 和 $Y$ 的一个公共子序列。注意对于任何给定的序列 $X$ 和 $Y$，空序列总是它们的一个公共子序列。

所有公共子序列问题是要求对于给定的 $2$ 个序列 $X=x_1x_2\ldots x_m$ 和 $Y=y_1y_2\ldots y_m$，找出 $X$ 和 $Y$ 的所有不同的公共子序列。

输入格式

文件的第一行有两个正整数 $m$ 和 $n$，分别表示两个输入序列 $X$ 和 $Y$ 的长度。

接下来的两行分别给出输入序列 $X=x_1x_2\cdots x_m$ 和 $Y=y_1y_2\cdots y_m$，其中序列中每个元素均为二十六个英文大小写字母。

文件的最后一行给出一个非负整数 $k$。

$k$ 的值为1时，表示计算结果要输出 $X$ 和 $Y$ 的所有不同的公共子序列，以及 $X$ 和 $Y$ 有多少个不同的公共子序列。

$k$ 的值为0时，表示计算结果只要输出 $X$ 和 $Y$ 有多少个不同的公共子序列。

输出

将计算出的 $X$ 和 $Y$ 的所有不同的公共子序列，或 $X$ 和 $Y$ 有多少个不同的公共子序列输出到文件中。当 $k=1$ 时，先输出 $X$ 和 $Y$ 的所有不同的公共子序列，每行输出一个公共子序列，按字典序从小到大输出。最后输出不同的公共子序列的个数。当 $k=0$ 时，只要输出不同的公共子序列的个数。

样例

样例输入 1

6 6
GCTACT
GATCCT 1

样例输出 1


A
AC
ACT
AT
C
CC
CCT
CT
G
GA
GAC
GACT
GAT
GC
GCC
GCCT
GCT
GT
GTC
GTCT
GTT
T
TC
TCT
TT
26

提示

数据范围与提示

$1\leq m,n\leq 3010$