TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4253
  • 题目
  • P4253牛的染色体
    限制 : 时间限制 : - MS   空间限制 : 165536 KB
    评测说明 : 1.5s
    问题描述

    约翰有N头斑点奶牛和N头黑牛。约翰研究了这些奶牛的基因组。每头奶牛的基因组都有M个字符来表示,表示基因的字符分别是A,C,G,T。例如,当N=3,M=8是,奶牛们的基因如下:

    编号     1  2  3  4  5  6  7  8
    斑牛1:A A T C C C A T
    斑牛2:A C T T G C A A
    斑牛3:G G T C G C A A

    黑牛1:A C T C C C A G
    黑牛2:A C T C G C A T
    黑牛3:A C T T C C A T

    约翰发现,他只需要观察基因中第[2,5]这段区间,就能将两种奶牛区分出来,因为任何一只班牛的基因和任何一只黑牛的基因在这段区间都是不相同的。

    对于给出的两种奶牛的基因组,请你帮约翰找出最短的一段区间,使得在这段区间中,任意一只班牛和任意一只黑牛的基因都不相同。输出这个区间的长度。

    输入格式

    第一行,两个整数N和M
    接下来N行,每行长度为M的字符串,表示一头斑牛的基因
    接下来N行,每行长度为M的字符串,表示一头黑牛的基因

    输出格式

    一个整数,表示所求答案。保证答案有解。

    样例输入

    3 8
    AATCCCAT
    ACTTGCAA
    GGTCGCAA
    ACTCCCAG
    ACTCGCAT
    ACTTCCAT

    样例输出

    4

    提示

    1≤N≤500    3≤M≤500


    来源  USACO 2017 US Open Contest, Gold