题目

Bovine Genomics

提交数: 14, 通过率: 21.43%, 平均分: 58.57

题目描述:

Farmer John owns Ncows with spots and N cows without spots. Having just completed a course in bovine

genetics, he is convinced that the spots on his cows are caused by mutations in the bovine genome.A

t great expense, Farmer John sequences the genomes of his cows. Each genome is a string of length Mb

uilt from the four characters A, C, G, and T. When he lines up the genomes of his cows, he gets a ta

ble like the following, shown here for N=3 and M=8:

Positions: 1 2 3 4 5 6 7 8

Spotty Cow 1: A A T C C C A T

Spotty Cow 2: A C T T G C A A

Spotty Cow 3: G G T C G C A A

Plain Cow 1: A C T C C C A G

Plain Cow 2: A C T C G C A T

Plain Cow 3: A C T T C C A T

Looking carefully at this table, he surmises that the sequence from position 2 through position 5 is

sufficient to explain spottiness. That is, by looking at the characters in just these these positio

ns (that is, positions 2…5), Farmer John can predict which of his cows are spotty and which are not

. For example, if he sees the characters GTCG in these locations, he knows the cow must be spotty.Pl

ease help FJ find the length of the shortest sequence of positions that can explain spottiness.

FJ拥有有斑点的牛和没有斑点的牛。他刚刚完成了牛基因的一门课程，他相信牛身上的斑点是由牛的基因突变引起

的。FJ花费了巨大的代价，将他的牛的基因组排序。每个基因组都是长度为M的字符串。当他把牛的基因组排列起

来的时候，他得到了一个像下面这样的表格，这里显示的是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

如果在某一段区间内，斑点牛和普通牛没有相同的基因段（即两组集合没有交集），那么FJ就能通过这段区间分辨两种牛。

请你帮FJ找出最短的满足条件的区间。

如样例

1~3 这段区间，斑点牛集合为{AAT,ACT,GGT},普通牛集合为{ACT,ACT,ACT} 斑点牛和普通牛都含有ACT这个字符串，不满足条件。

2~5 这段区间，斑点牛集合为{ATCC,CTTG,GTCG}，普通牛集合为{CTCC,CTCG,CTTC} 无公共字符串，满足条件。

输入格式:

The first line of input contains N(1≤N≤500) and M (3≤M≤500). The next N lines each contain a str

ing of M characters; these describe the genomes of the spotty cows. The final Nlines describe the ge

nomes of the plain cows. No spotty cow has the same exact genome as a plain cow.

输入的第一行包含N(1≤N≤500)和M(3≤≤500)。

接下来的N行，每行一个由M个字符组成的字符串，描述了斑牛的基因组。

最后N行描述了普通奶牛的基因组。

输出格式:

Please print the length of the shortest sequence of positions that is sufficient to explain spottine

ss. A sequence of positions explains spottiness if the spottiness trait can be predicted with perfec

t accuracy among Farmer John's population of cows by looking at just those locations in the genome.

输出仅一行，满足条件的最短区间的长度。

样例输入:

3 8
AATCCCAT
ACTTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

样例输出:

时间限制: 1000ms
空间限制: 128MB

来源: Usaco2017 Open Gold