NOIP 复赛之前,HSD 桑进行了一项研究,发现人某条染色体上的一段 DNA 序列中连续的 k 个碱基组成的碱基序列与做题的 AC 率有关!于是他想研究一下这种关系。 现在给出一段 DNA 序列,请帮他求出这段 DNA 序列中所有连续 k 个碱基形成的碱基序列中,出现最多的一种的出现次数。
两行,第一行为一段 DNA 序列,保证 DNA 序列合法,即只含有 A, G, C, T 四种碱基; 第二行为一个正整数 k ,意义与题目描述相同。
A
G
C
T
一行,一个正整数,为题目描述中所求答案。
AAAAA 1
5
对于这段 DNA 序列,连续的 1 个碱基组成的碱基序列只有 A,共出现 5 次,所以答案为 5 。
ACTCACTC 4
2
对于这段 DNA 序列,连续的 4 个碱基组成的碱基序列为:ACTC, CTCA, TCAC 与 CACT。其中 ACTC 出现 2 次,其余均出现 1 次,所以出现最多的次数为 2 ,即为答案。
ACTC
CTCA
TCAC
CACT
记 DNA 序列长度为 n 。 本题共 10 组数据,只有输出与标准输出一致才可以获得该测试点的分数。
下面给出每组数据的范围和满足性质情况:
性质:给出的 DNA 碱基序列中每个碱基均相同。 对于所有数据均保证 k\le n