ZZULIOJ - 18新利直播

题目描述

地理项目是 IBM 和国家地理学会的合作研究项目，从成千上万捐献的 DNA 分析地球上人类是如何繁衍的。

作为一名 IBM 的研究人员，请你写一个程序找到给定的 DNA 片段之间的相同之处，使得对个体的调查相关联。

一个 DNA 碱基序列是指把在分子中发现的氮基的序列给罗列出来。有四种氮基：腺嘌呤（ A ），胸腺嘧啶（ T ），鸟嘌呤（ G ）和胞嘧啶（ C ），例如，一个 6 碱基 DNA 序列可以表示为 TAGACC 。

给出一个 DNA 碱基序列的集合，确定在所有序列中都出现的最长的碱基序列。

输入

输入的第一行给出了整数 n ，表示测试数据集合的数目。每个测试数据集合由下述两部分组成：

一个正整数 m (2 <= m <= 10) ，给出数据集合中碱基序列的数目。

m 行，每行给出一个 60 碱基的碱基序列。

输出

对于输入的每个测试数据集合的所有的碱基序列，输出最长的相同的碱基子序列。如果最长的相同的碱基子序列的长度小于 3 ，则输出“ no significant commonalities ”来代替碱基子序列。如果相同最长长度的子序列有多个，则仅输出按字母排序的第一个。

样例输入 Copy

3 2 GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA 3 GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA GATACTAGATACTAGATACTAGATACTAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA GATACCAGATACCAGATACCAGATACCAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA 3 CATCATCATCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC ACATCATCATAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AACATCATCATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

样例输出 Copy

no significant commonalities AGATAC CATCATCAT

来源/分类

South_Central_USA_2006

1409: Blue Jeans