#U1003. [USACO17Open]Bovine Genomics B

[USACO17Open]Bovine Genomics B

题目背景

农场主约翰拥有 N 头有斑点的奶牛和 N 头没有斑点的奶牛。他刚刚完成了牛遗传学的课程,深信奶牛身上的斑点是由牛基因组中一个位置的突变引起的。

约翰农场主花费巨资对奶牛的基因组进行了测序。每个基因组都是由 A、C、G 和 T 四个字符组成的长度为 M 的字符串。当他把奶牛的基因组排成一行时,他得到了如下表格,这里显示的是 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 A ... G
普通牛 2:A C T C G C A ... T
普通牛 3:A C T T C A ... T

仔细观察这个表格,他推测位置 2 是基因组中可以解释斑点性的一个潜在位置。也就是说,通过观察这个位置上的特征,约翰农场主可以预测他的牛中哪些有斑点,哪些没有(这里,A 或 G 表示有斑点,C 表示平淡无奇;T 与此无关,因为它没有出现在约翰农场主的任何一头牛的第 2 个位置上)。位置 1 本身不足以解释斑点性,因为该位置上的 A 可能表示斑点牛,也可能表示普通牛。

给定约翰农夫的奶牛基因组,请计算有多少个位置本身可以解释斑点性。

输入格式(文件 cownomics.in):

第一行输入 N 和 M,均为正整数,大小最多为 100。接下来的 N 行每行包含一个由 M 个字符组成的字符串;这些字符串描述了多斑奶牛的基因组。最后 N 行描述普通奶牛的基因组。

输出格式(文件 cownomics.out):

请计算基因组中可能解释斑点性的位置数(0...M 范围内的整数)。如果在约翰农场主的奶牛群体中,仅通过基因组中的这一个位置就能完全准确地预测出奶牛的斑点性状,则该位置有可能解释斑点性状。

样例

3 8
AATCCCAT
GATTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT
1