#537. 「LibreOJ NOIP Round #1」DNA 序列

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: HeRaNO

题目描述

NOIP 复赛之前,HSD 桑进行了一项研究,发现人某条染色体上的一段 DNA 序列中连续的 kk 个碱基组成的碱基序列与做题的 AC 率有关!于是他想研究一下这种关系。
现在给出一段 DNA 序列,请帮他求出这段 DNA 序列中所有连续 kk 个碱基形成的碱基序列中,出现最多的一种的出现次数。

输入格式

两行,第一行为一段 DNA 序列,保证 DNA 序列合法,即只含有 A, G, C, T 四种碱基;
第二行为一个正整数 kk,意义与题目描述相同。

输出格式

一行,一个正整数,为题目描述中所求答案。

样例

样例输入 1

AAAAA
1

样例输出 1

5

样例解释 1

对于这段 DNA 序列,连续的 11 个碱基组成的碱基序列只有 A,共出现 55 次,所以答案为 55

样例输入 2

ACTCACTC
4

样例输出 2

2

样例解释 2

对于这段 DNA 序列,连续的 44 个碱基组成的碱基序列为:ACTC, CTCA, TCACCACT。其中 ACTC 出现 22 次,其余均出现 11 次,所以出现最多的次数为 22,即为答案。

数据范围与提示

记 DNA 序列长度为 nn
本题共 1010 组数据,只有输出与标准输出一致才可以获得该测试点的分数。

下面给出每组数据的范围和满足性质情况:

测试点编号 nn kk 其他
11 =105=10 ^5 =1=1 满足性质
2,32,3 5×105\le 5 \times 10 ^5 =1=1 -
44 5×105\le 5 \times 10 ^5 10\le 10 满足性质
5,6,7,85,6,7,8 106\le 10 ^6 10\le 10 -
9,109,10 =5×106=5 \times 10 ^6 =10=10 -

性质:给出的 DNA 碱基序列中每个碱基均相同。
对于所有数据均保证 knk\le n