问题6705--牛基因组

6705: 牛基因组

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 256 MiB

题目描述

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

农场主约翰花费巨资对他的奶牛进行了基因组测序。每个基因组是由四个字符ACGT组成的。当他排列他的奶牛的基因组时,他得到如下表,如这里所示,N=3

位置:    1 2 3 4 5 6  7…M

斑点牛1: A A T C C C AT

斑点牛2:G A T T G C AA

斑点牛3:G G T C G C AA

普通牛1:A C T C C C AG

普通牛2:A C T C G C AT

普通牛3:A C T T C C AT

仔细观察这张表,他推测位置2是基因组中可能解释斑点的潜在位置。也就是说,通过观察这个位置的角色,农民约翰可以预测他的奶牛中哪些是斑点,哪些不是斑点(这里,AG表示斑点,C表示普通;T不相关,因为它不会出现在农民约翰在位置2的任何奶牛中)。位置1本身不足以解释斑点,因为该位置的A可能表示斑点奶牛或普通奶牛。

考虑到农民约翰的奶牛的基因组,请计算可能单独解释斑点的位置的数量。



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

输入的第一行包含NM,这两个都是最大为100的正整数。接下来的N行各包含一个由M个字符组成的字符串;这些描述了斑点牛的基因组。最后的N行描述了普通牛的基因组。

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

请计算基因组中可能解释斑点的位置数(0M范围内的整数)。如果通过观察基因组中的这一个位置,农民约翰的奶牛群体中的斑点性状可以完全准确地预测,那么一个位置可能解释斑点。

 

示例输入:

3 8

AATCCCAT

GATTGCAA

GGTCGCAA

ACTCCCAG

ACTCGCAT

ACTTCCAT

 

示例输出:

1

样例输入 复制


样例输出 复制


来源/分类