2011年9月29日 星期四

11961 - DNA

DNA有四種鹼基:A, C, G, T。給定長度為N的DNA序列,我們說此DNA的「第K突變(K-th mutation)」表示此DNA可藉由原始DNA改變K個元素來得到,例如GAT為GGT的第一突變,為TTT的第二突變。

給定一原始的DNA序列,及最大的突變數K,請你列出所有可能的組合(包含第0~K突變)。

INPUT

輸入的第一列有一整數T(T <= 50)表示測試資料的組數,每組資料兩列,第一列有兩個整數N(N <= 10),K(K <= 5),第二列為長度N的原始DNA序列。

OUTPUT

請每組測試資料輸出所有組合的總數,並以字典順序由小到大輸出所有組合。

SAMPLE INPUT

1
3 1
AAA

SAMPLE OUTPUT

10
AAA
AAC
AAG
AAT
ACA
AGA
ATA
CAA
GAA
TAA

原文出處

沒有留言:

張貼留言