「LibreOJ NOIP Round #1」DNA 序列 - 题目 - HelloWorld信息学奥赛题库

题目描述

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

输入格式

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

输出格式

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

样例 1

input

AAAAA
1

output

对于这段 DNA 序列，连续的 $1$ 个碱基组成的碱基序列只有 A，共出现 $5$ 次，所以答案为 $5$。

样例 2

input

ACTCACTC
4

output

对于这段 DNA 序列，连续的 $4$ 个碱基组成的碱基序列为：ACTC, CTCA, TCAC 与 CACT。其中 ACTC 出现 $2$ 次，其余均出现 $1$ 次，所以出现最多的次数为 $2$，即为答案。

数据范围与提示

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

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

测试点编号	$n$	$k$	其他
$1$	$=10 ^5$	$=1$	满足性质
$2,3$	$\le 5 \times 10 ^5$	$=1$	-
$4$	$\le 5 \times 10 ^5$	$\le 10$	满足性质
$5,6,7,8$	$\le 10 ^6$	$\le 10$	-
$9,10$	$=5 \times 10 ^6$	$=10$	-

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

HelloWorld信息学奥赛题库