ACM-ICPC 2008 Seoul Regional- MCS > 문제은행 : 정보올림피아드&알고리즘



1155 : MCS

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
109 회   
시도횟수
361 회   

문제

ACGT로만 이루어진 염기서열(DNA sequence)이 존재한다.
염기 서열에서 만들 수 길이가 k인 부분문자열(substring: 문자열 내에서 연속된 부분을 잘라서 만들 수 있는 문자열)들 중에서 

사용한 문자의 순서가 다르더라도, 사용한 각 문자들의 빈도가 일치할 경우 두개의 부분문자열을 유사한 것으로 친다고 하자.
이 경우 가장 많이 등장하는 유사한 길이 k의 부분문자열의 빈도수를 구하는 프로그램을 작성하라.

 

예를 들어 염기서열이 "GCAGGAGCGCCAGG"라고 주어졌을 경우 가능한 길이가 3인 부분 문자열은

GCA, CAG, GGA, GAG,…, CAG등이 존재하고, 

AGG와 GGA, GAG 그리고 AGG가 유사하기 때문에 이 경우 4개의 서로 유사한 부분문자열이 존재한다.


입력형식

입력의 첫 번째 줄에는 k(1≤k≤1,000)가 입력된다. 

그 다음 줄에는 길이 60,000이하의 A와 C, G 그리고 T로 이뤄진 염기서열 문자열이 입력된다.


출력형식

입력된 염기서열 안에서 가장 많이 등장하는 길이 k의 부분문자열의 등장횟수를 출력한다.


입력 예

3 
GCAGGAGCGCCAGG

출력 예

4


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP