题目描述
农夫约翰拥有N头有斑点的牛和N头没有斑点的牛。刚刚完成了一门牛遗传学课程,他确信他的牛身上的斑点是由牛基因组中单一位置的突变引起的。
农场主约翰花费巨资对他的奶牛进行了基因组测序。每个基因组是由四个字符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的任何奶牛中)。位置1本身不足以解释斑点,因为该位置的A可能表示斑点奶牛或普通奶牛。
考虑到农民约翰的奶牛的基因组,请计算可能单独解释斑点的位置的数量。
输入格式(文件cownomics.in):
输入的第一行包含N和M,这两个都是最大为100的正整数。接下来的N行各包含一个由M个字符组成的字符串;这些描述了斑点牛的基因组。最后的N行描述了普通牛的基因组。
输出格式(文件cownomics.out):
请计算基因组中可能解释斑点的位置数(0…M范围内的整数)。如果通过观察基因组中的这一个位置,农民约翰的奶牛群体中的斑点性状可以完全准确地预测,那么一个位置可能解释斑点。
示例输入:
3 8
AATCCCAT
GATTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT
示例输出:
1
样例输入 复制
样例输出 复制