P6705: 牛基因组
传统题
1.000s
时间限制
256MB
内存限制
14 提交
7 解决
【题目描述】
农夫约翰拥有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