分析如DNA序列这样的生命科学数据是计算机的一个有趣应用。从生物学的角度上说,DNA 是一种由腺嘌呤、胞嘧啶
、鸟嘌呤和胸腺嘧啶这四种核苷酸组成的链式结构。这四种核苷酸分别用大写字母A、C、G、T表示。这样,一条DNA
单链可以被表示为一个只含以上四种字符的字符串。我们将这样的字符串称作一个DNA序列 。有时生物学家可能无
法确定一条DNA单链中的某些核苷酸。在这种情况下,字符N将被用来表示一个不确定的核苷酸。换句话说,N可以用
来表示A、C、G、T中的任何一个字符。我们称包含一个或者多个N的DNA序列为未完成序列;反之,就称作完成序列。
如果一个完成序列可以通过将一个未完成序列中的每个N任意替换成A、C、G、T得到的话,就称完成序列适合这个未
完成序列。举例来说,ACCCT适合ACNNT,但是AGGAT不适合。研究者们经常按照如下方式排序四种核苷酸:A优先于C,C
优先于G,G优先于T。如果一个DNA序列中的每个核苷酸都与其右边的相同或者优先,就将其归类为范式-1。举例来说
,AACCGT是范式-1,但是AACGTC不是。一般来说,一个DNA序列属于范式-j(j>1),只要它属于范式-(j-1)或者是一个范
式-(j-1)和一个范式-1的连接。举例来说,AACCC、ACACC和ACACA都是范式-3,但GCACAC和ACACACA不是。同样,研究
者们按照字典序对 DNA 序列进行排序。按照这个定义,最小的属于范式-3的DNA序列是AAAAA,最大的是TTTTT。这里
是另外一个例子,考虑未完成序列 ACANNCNNG。那么前7个适合这个未完成序列的DNA序列是:
ACAAACAAG
ACAAACACG
ACAAACAGG
ACAAACCAG
ACAAACCCG
ACAAACCGG
ACAAACCTG
写一个程序,找到按字典序的第R个适合给定的长度为M的未完成序列的范式-K。
BZPRO