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

题目描述

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列 $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=$``GACT`` 是序列 $X=$``GCTACT`` 的子序列,相应的递增下标序列为 $1,4,5,6$。给定两个序列 $X$ 和 $Y$,当另一序列 $Z$ 既是 $X$ 的子序列又是 $Y$ 的子序列时,称 $Z$ 是序列 $X$ 和 $Y$ 的公共子序列。例如,若 $X=$``GCTACT``, $Y=$``GATCCT``,序列 $T$ 是 $X$ 和 $Y$ 的一个公共子序列,序列 ``GACT`` 也是 $X$ 和 $Y$ 的一个公共子序列。注意对于任何给定的序列 $X$ 和 $Y$,空序列总是它们的一个公共子序列。 所有公共子序列问题是要求对于给定的 $2$ 个序列 $X=x_1x_2\ldots x_m$ 和 $Y=y_1y_2\ldots y_m$,找出 $X$ 和 $Y$ 的所有不同的公共子序列。

输入输出格式

输入格式


文件的第一行有两个正整数 $m$ 和 $n$,分别表示 $2$ 个输入序列 $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$ 答案....很大啦