OpenJudge

3:牛仔裤

总时间限制:
1000ms
内存限制:
65536kB
描述

基因地理计划是IBM和美国国家地理学会的合作研究项目,用来分析来自于数十万的捐助者的DNA,来研究人类在地球上的迁移图。

作为一个IBM的研究者,你被要求写一个程序,来发现共性的DNA片段,用来和个人调查信息关联以确定新的遗传标记。

DNA碱基序列通过按顺序排列分子中发现的含氮碱基来记录。有四种碱基:腺嘌呤(A),胸腺嘧啶(T),鸟嘌呤(G)和胞嘧啶(C)。一个6碱基的DNA序列可以表示为TAGACC

给定一组DNA的碱基序列,确定发生在所有序列中最长的一系列碱基。


输入
输入以一个整数n作为单独的一行来开头,表示数据集个数。每个数据集包括以下成分:
一个正整数m(2<=m<=10)表示数据集中碱基序列个数
m行,每行包括一个含有60个碱基的序列
输出
对于每一个数据集,输出所有碱基序列中共同的最长的子碱基序列。如果这个最长的共同碱基子序列比三要小,则输出”no significant commonalities”以代替。如果存在多个相同长度的最长共同碱基子序列存在,则只输出按字母顺序排列的第一个序列。
样例输入
3
2
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
3
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
GATACTAGATACTAGATACTAGATACTAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
GATACCAGATACCAGATACCAGATACCAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
3
CATCATCATCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
ACATCATCATAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AACATCATCATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
样例输出
no significant commonalities
AGATAC
CATCATCAT
全局题号
6452
提交次数
2
尝试人数
1
通过人数
1

Other language verions