Problem1203--22-数组-3-DNA序列

1203: 22-数组-3-DNA序列

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Solved: 3Submit: 2628Statistics

Description

小南的导师是做生物信息学的，给了小南m个长度均为n的DNA序列（只包含A、C、G、T），要小南找到一个新的长度为n的DNA序列，使其到所有m个已知的DNA序列的总憨憨距离最小。
憨憨距离的定义为: 两个等长字符串的憨憨距离等于字符不同的位置个数。
例如下面这两个DNA序列的憨憨距离为2。 
TATGATAC
TAAGCTAC

Input

多组样例。样例数由输入的第一个整数t确定。 
对于每一组样例，第一行输入整数m和n（4≤m≤50，4≤n≤1000）。
接下来m行每行一个长度为n的DNA序列(只包含A、C、G、T)。

Output

对于每一组测试用例，输出让憨憨距离最小的DNA序列和其对应的距离。若有多个DNA序列，输出字典序最小的解。

Sample Input Copy 

3
5 8
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT
4 10
ACGTACGTAC
CCGTACGTAG
GCGTACGTAT
TCGTACGTAA
6 10
ATGTTACCAT
AAGTTACGAT
AACAAAGCAA
AAGTTACCTT
AAGTTACCAA
TACTTACCAA

Sample Output Copy 

TAAGATAC
7
ACGTACGTAA
6
AAGTTACCAA
12

Source/Category

简单 字符串处理 
Submit