P3667 [USACO17OPEN] Bovine Genomics G

Farmer John 拥有 $N$ 头有斑点的牛和 $N$ 头没有斑点的牛。他刚刚完成了一门关于牛遗传学的课程，并确信他牛身上的斑点是由牛基因组中的突变引起的。 Farmer John 花费巨资对他的牛进行了基因组测序。每个基因组是一个由字符 A、C、G 和 T 组成的长度为 $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 ``` 仔细观察这个表格后，他推测从位置 2 到位置 5 的序列足以解释斑点现象。也就是说，通过仅查看这些位置（即位置 $2 \ldots 5$）的字符，Farmer John 可以预测哪些牛是有斑点的，哪些是没有斑点的。例如，如果他在这些位置看到字符 GTCG，他就知道这头牛一定是有斑点的。 请帮助 Farmer John 找到能够解释斑点现象的最短位置序列的长度。

无

无