P6944: 牛基因序列
传统题
1.000s
时间限制
256MB
内存限制
1 提交
1 解决
【题目描述】
【题目描述】
农夫约翰有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 C A…G
普通牛2:A G T T G C A…T
普通牛3:A G T T C C A…T
仔细观察这张表格，他推测位置2和4足以解释斑点现象。也就是说，通过观察这两个位置的字符，农民约翰可以预测他的奶牛中哪些有斑点，哪些没有(例如，如果他看到G和C，奶牛一定是有斑点的)。
农夫约翰相信，斑点现象不能仅用基因组中的一两个位置来解释，而是可以通过观察三个不同的位置来解释。请帮他数一数有多少组不同的位置可以解释斑点。
【输入格式】(cownomics.in)
第一行输入包含N(1≤N≤500)和M(3≤M≤50)。接下来的N行每一行包含一个M个字符的字符串;这些描述了斑点牛的基因组。最后N行描述了普通奶牛的基因组。
【输出格式】(cownomics.out)
请输出可以解释斑点的三个不同位置的集合的数量。如果仅仅通过观察基因组中的这三个位置，就可以在农民约翰的奶牛种群中完美准确地预测斑点特征，那么就可以用一组三个位置来解释斑点特征。
【样例输入】:
3 8
AATCCCAT
GATTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT
样例输出:
22