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} 无公共字符串，满足条件。
