#1875 최빈도 K-substring 찾기

60  40 s   256 MB  

Description

알파벳 'a', 'c', 'g', 't' 의 조합으로 이뤄진 길이 N의 문자열이 존재할 때 가장 많이 등장하는 K-substring(길이가 K인 substring, substring의 정의는 http://en.wikipedia.org/wiki/Substring 를 참고할 것) 의 빈도수를 찾는 프로그램을 작성하라.

가령 'aaaacgaagtaaa' 와 같은 문자열이 있을 경우, K = 3 일 때 존재할 수 있는 substring은 다음과 같다.

aaa, aac, acg, cga, gaa, aag, agt, gta, taa
이 중에서 aaa의 경우 다음과 같이 총 3번 등장하기 때문에 이 경우의 답은 3이 된다.
aaaacgaagtaaa
aaaacgaagtaaa
aaaacgaagtaaa
 

Input

입력은 총 두줄로 주어진다.

입력의 첫 줄에는 N과 K가 입력된다( 1 ≤ N ≤ 2×106 , 1 ≤ K ≤ 10 ).

입력의 두번째 줄에는 길이 N의 문자열이 주어지며, 알파벳 'a', 'c', 'g', 't' 으로만 이뤄져 있다.

Output

입력에 대해 가장 많이 등장하는 K-substring의 빈도수를 출력한다.

Sample Input

Sample Output

13 3
aaaacgaagtaaa
3

HINT

과제 제출 시 반드시 다음의 코드에 기반하여 프로그램을 작성해야 한다.

http://ideone.com/FgXb0

주어진 코드를 사용하지 않거나, 주어진 코드에 수정하지 말아야 할 부분을 수정하여 과제를 제출할 경우 무효 처리 한다.