#U1617OB2. Bovine Genomics

Bovine Genomics

Farmer John 拥有 N 头有斑点的奶牛和 N 头没有斑点的奶牛。刚刚完成牛遗传学课程后,他确信他的奶牛身上的斑点是由牛基因组中单个位置的突变引起的。

Farmer John 花费巨资对他的奶牛的基因组进行了测序。每个基因组是一个长度为 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 是基因组中可以解释斑点的潜在位置。也就是说,通过观察这个位置的角色,Farmer John 可以预测他的哪些奶牛有斑点,哪些没有(这里,A 或 G 表示有斑点,C 表示无斑点;T 是无关紧要的,因为它没有出现在任何Farmer John 的奶牛在位置 2)。位置 1 本身不足以解释斑点,因为该位置的 A 可能表示斑点牛或无斑点奶牛。

鉴于 Farmer John 的奶牛的基因组,请计算可能单独解释斑点的位置数量。

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

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

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

请计算基因组中可能解释斑点的位置数(0…M 范围内的整数)。如果仅通过查看基因组中的这一位置,就可以在 Farmer John 的奶牛群中完全准确地预测斑点特征,则该位置可能解释斑点。

样例输入:

3 8
AATCCCAT
GATTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

样例输出:

1