TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1479
  • 题目
  • P1479Blue Jeans(蓝色牛仔裤)
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    IBM和“国家地理”杂志共同研究的一个名为“蓝色牛仔裤”的项目,就是分析成千上万个捐赠的DNA,以便找出世界的人口是怎样构成和分布的。
    作为IBM的一名研究员,你的任务就是写一个程序来研究不同DNA片段间的联系。
    一个DNA序列由A、T、G、C四个字母来表示,比如“TAGACC”是一种长度为6的DNA序列。

    告诉你若干条DNA序列,请找出最长的一段连续DNA序列,该序列出现在了给出的所有DNA序列中(注:也就是求最长公共子串)。

    输入格式

    第一行,一个整数n,表示下面有n组测试数据n<=20
    对于每组测试数据:
    第一行,一个整数m (2 <= m <= 10),表示告诉你了m条DNA序列。
    接下来m行,每行表示一条DNA序列,每行的长度不超过60

    输出格式

    对于每组测试数据,输出它的最长公共子串。
    如果子串的长度小于3,输出"no significant commonalities"
    如果有多条长度相等的最长子串,输出字典序最小的那条。

    样例输入

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

    样例输出

    no significant commonalities
    AGATAC
    CATCATCAT


    来源  South Central USA 2006 翻译by helang