2016年蓝桥杯国赛Java B组碱基问题

问题描述

碱基

当前，研究人员正在对n个物种的遗传信息展开分析。
对于第i个物种而言，其DNA序列被标记为s[i]，其中第j个位置上的碱基记作s[i][j]，该碱基只能是A、T、G或C中的一种。
科研人员希望识别出这些生物群体中某些共同特征，当前重点关注的是那些在至少m个物种中出现过的长度为k的连续碱基片段。具体而言，科学家所关注的序列可表示为2m元组(i1,p1,i2,p2…im,pm)，
需满足以下条件：
1<=i1<i2<…<im<=n;
并且对于任意q(0<=q<k)，有s[i1][p1+q]=s[i2][p2+q]=…=s[im][pm+q]。

现提供所有生物的DNA序列，请计算符合上述要求的2m元组总数。若两个2m元组在任意一个位置上存在差异，则视为不同的元组。

问题分析

题目的基本含义是
提供n个由A、T、G、C这四个字符构成的字符串，设定一种情形：在这些字符串中有m个包含长度为k的共同子串 ，需要计算这样的情形共有多少种。（需要注意的是，例如字符串AAAA中，前三个A和后三个A被视为两个不同的子串）

分析题目中提供的例子
n = 4，m = 3，k = 3
这n个字符串分别为
①AAA
②AAAA
③AAA
④AAA
显然，这个长度为k的公共子串为AAA，而该子串在各个字