Bovine Genomics

题目描述

农夫约翰有 $N$ 头有斑点的奶牛和 $N$ 头没有斑点的奶牛。刚上完一门牛类遗传学课程，他坚信奶牛身上的斑点是由牛基因组中某一个位置的突变造成的。

农夫约翰花费巨资对奶牛的基因组进行测序。每个基因组是一个长度为 $M$ 的字符串，由 A、C、G、T 四种字符构成。当他把奶牛的基因组按位置对齐后，会得到如下所示的一张表（这里以 $N=3$ 为例）：位置： 1 2 3 4 5 6 7 ... M

有斑奶牛 1：A A T C C C A ... T 有斑奶牛 2：G A 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 位是一个可能解释斑点性状的基因组位置。也就是说，只看这个位置上的字符，农夫约翰就能预测哪些奶牛有斑点、哪些没有（这里 A 或 G 表示有斑，C 表示无斑；T 不相关，因为在农夫约翰的奶牛中，第 2 位没有出现 T）。

第 1 位本身不足以解释斑点性状，因为该位置上出现 A 可能表示有斑奶牛，也可能表示无斑奶牛。

给定农夫约翰奶牛的基因组，请你统计有多少个位置可以单独作为潜在原因来解释斑点性状。

第一行包含 $N$ 和 $M$ ，均为不超过 100 的正整数。接下来的 $N$ 行每行包含一个长度为 $M$ 的字符串，描述有斑奶牛的基因组。最后 $N$ 行描述无斑奶牛的基因组。

请输出基因组中可能解释斑点性状的位置数量（一个在 $0 \ldots M$ 范围内的整数）。如果仅通过观察基因组中某一个位置，就能在农夫约翰的奶牛群体中以 100% 的准确率预测斑点性状，则该位置被认为可能解释斑点性状。

3 8
AATCCCAT
GATTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

题目来源：Brian Dean

标签: USACO|2017|Bronze

USACO|2017|Bronze