C1087 - DNA序列
题目描述
DNA（脱氧核糖核酸）是一种包含遗传指令的分子。它由四种不同的核苷酸组成，分别是腺嘌呤(Adenine)、胸腺嘧啶(Thymine)、鸟嘌呤(Guanine)和胞嘧啶(Cytosine)，如图1所示。如果用它们的首字母表示核苷酸，DNA链可以看作是由四个字符A、T、G和C组成的长字符串（字符序列）。
例如，假设我们给出了一段由以下核苷酸序列组成的DNA链：
“Thymine-Adenine-Adenine-Cytosine-Thymine-Guanine-CytosineCytosine-Guanine-Adenine-Thymine” （胸腺嘧啶-腺嘌呤-腺嘌呤-胞嘧啶-胸腺嘧啶-鸟嘌呤-胞嘧啶-胞嘧啶-鸟嘌呤-腺嘌呤-胸腺嘧啶）
然后我们可以用字符串“TAACTGCCGAT”来表示上述DNA链。
生物学家Ahn教授发现，基因X普遍存在于五种不同动物的DNA链中，分别是狗、猫、马、牛和猴子。他还发现，每种动物的基因X的DNA序列非常相似。见图2。
安教授认为人类也可能拥有基因X，并决定在人体DNA中寻找基因X的DNA序列。然而，在搜索之前，他需要定义一个基因X的代表性DNA序列，因为在五种动物的DNA中，这些序列并不完全相同。他决定使用汉明距离来定义代表性序列。
汉明距离是指两个等长字符串在各个位置上字符不同的个数。例如，假设我们有两个字符串“AGCAT”和“GGAAT”。这两个字符串的汉明距离是2，因为它们的第1个和第3个字符不同。使用汉明距离，我们可以为一组等长字符串定义一个代表字符串。假设给定一组长度为n的字符串S = {s1, ..., sm}，一个长度为n的字符串y与集合S之间的共识误差是y与S中每个si的汉明距离之和。如果y与S之间的共识误差在所有可能的长度为n的字符串y中最小，那么y就称为S的共识字符串。例如，给定三个字符串“AGCAT”、“AGACT”和“GGAAT”，它们的共识字符串是“AGAAT”，因为“AGAAT”与这三个字符串的汉明距离之和是最小的3。（在这种情况下，共识字符串是唯一的，但一般来说，可能会有不止一个共识字符串。）我们使用共识字符串作为DNA序列的代表。例如，图2中的基因X的共识字符串是“GCAAATGGCTGTGCA”，共识误差是7。
输入格式
你的程序需要从标准输入中读取数据。
输入由T个测试用例组成。输入的第一行给出了测试用例的数量T。每个测试用例的开始是一行包含两个由单个空格分隔的整数m和n。整数m (4 ≤ m ≤ 50) 代表DNA序列的数量，整数n (4 ≤ n ≤ 1000) 代表DNA序列的长度。在接下来的m行中，每行给出一个DNA序列。
输出格式
在每个测试用例的第一行打印共识字符串，在第二行打印共识误差。如果存在多个共识字符串，打印字典序最小的共识字符串。
输入输出样例
| 输入样例 | 输出样例 |
|---|---|
| 3 5 8 TATGATAC TAAGCTAC AAAGATCC TGAGATAC TAAGATGT 4 10 ACGTACGTAC CCGTACGTAG GCGTACGTAT TCGTACGTAA 6 10 ATGTTACCAT AAGTTACGAT AACAAAGCAA AAGTTACCTT AAGTTACCAA TACTTACCAA |
TAAGATAC 7 ACGTACGTAA 6 AAGTTACCAA 12 |
数据范围与提示
对于100%的数据满足：$1 \le T \le 20$
测试点数目
共10个测试点，每个测试点10分
时间与内存限制
每个测试点时间：1000ms（1.0s），内存：256MiB
输入输出模式
本OJ支持两种输入输出模式