Extra
Time
所有公共子序列问题 Time:3s Memory:1024M AC:0% Submit:0

★问题描述:
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序
列X= 1 x 2 x … m x ,则另一序列Z= 1 z 2 z … k z 是X的子序列是指存在一个严格递增下标序列
1 i , 2 i ,…, k i 使得对于所有j=1,2,…,k有j ij z  x 。例如,序列Z=GACT是序列X= GCTACT的子
序列,相应的递增下标序列为1,4,5,6。给定2个序列X和Y,当另一序列Z既是X的子序列又是
Y的子序列时,称Z是序列X和Y的公共子序列。例如,若X= GCTACT,Y= GATCCT,序列
TT是X和Y的一个公共子序列,序列GACT也是X和Y的一个公共子序列。注意对于任何给定
的序列X和Y,空序列总是它们的一个公共子序列。
所有公共子序列问题是要求对于给定的2个序列X= 1 x 2 x … m x 和Y= 1 y 2 y … n y ,找出X
和Y的所有不同的公共子序列。
★编程任务:
对于给定的2个序列X= 1 x 2 x … m x 和Y= 1 y 2 y … n y ,根据输入数据的要求,找出它们所
有不同的公共子序列,或计算出它们有多少个不同的公共子序列。
★数据输入:
输入文件名为allcs.in。
文件的第一行有2个正整数m和n,(1<=m,n<=3010),分别表示2个输入序列X和Y的长度。
接下来的2行分别给出输入序列X= 1 x 2 x … m x 和Y= 1 y 2 y … n y 。其中序列中每个元素均为26
个英文大小写字母。文件的最后一行给出一个非负整数k。k的值为1时,表示计算结果要输
出X和Y的所有不同的公共子序列,以及X和Y有多少个不同的公共子序列。k的值为0时,表
示计算结果只要输出X和Y有多少个不同的公共子序列。
★结果输出:
输出文件名为allcs.out。
将计算出的X和Y的所有不同的公共子序列,或X和Y有多少个不同的公共子序列输出到
文件中。当k=1时,先输出X和Y的所有不同的公共子序列,每行输出1个公共子序列,按字
典序从小到大输出。最后输出不同的公共子序列的个数。当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
输入示例2
6 6
GCTACT
GATCCT
0

输出示例2
26