Bovine Genomics

题目描述

Farmer John 拥有 $N$ 头有斑点的奶牛和 $N$ 头没有斑点的奶牛。刚刚完成一门关于牛遗传学的课程后，他坚信奶牛身上的斑点是由牛基因组中的突变导致的。

Farmer John 花费巨大代价对他的奶牛进行了基因组测序。每个基因组都是一个长度为 $M$ 的字符串，由四种字符 A、C、G、T 构成。当他将奶牛的基因组对齐时，会得到如下表格（这里展示的是 $N=3$、$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

仔细观察这张表后，他推测从位置 2 到位置 5 的序列足以解释斑点性状。也就是说，只看这些位置上的字符（即位置 $2 \ldots 5$），Farmer John 就能预测他的奶牛哪些是有斑点的、哪些不是。例如，如果他在这些位置看到字符 GTCG，他就知道这头牛一定是有斑点的。

请帮助 FJ 找到能够解释斑点性的最短连续位置序列的长度。

输入格式

第一行输入包含 $N$ ($1 \leq N \leq 500$) 和 $M$ ($3 \leq M \leq 500$)。接下来 $N$ 行每行包含一个长度为 $M$ 的字符串；这些描述有斑点奶牛的基因组。最后 $N$ 行描述无斑点奶牛的基因组。不存在任何一头有斑点奶牛与某头无斑点奶牛拥有完全相同的基因组。

输出格式

请输出能够解释斑点性的最短连续位置序列的长度。

如果仅通过查看基因组中这些位置，就能在 Farmer John 的奶牛群体中以完全准确的方式预测斑点性状，则称这一段位置序列能够解释斑点性状。

3 8
AATCCCAT
ACTTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

4

提示

题目致谢：Brian Dean

标签: USACO|2017|Gold

来源

USACO|2017|Gold