시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 16 MB357594323.497%

문제

길이 n(1 ≤ n ≤ 1,000)인 염기서열이 있다. 이는 A, G, C, T로 구성되어 있는 문자열이라 생각할 수 있다. 주어진 염기서열의 부분 염기서열은, 염기서열을 문자열로 생각했을 때 부분문자열과 같이 정의되어 있다. 예를 들면 "AGCT"의 부분 염기서열은 "AG", "GC", "AGC", "AGCT" 등이 있다.

주의할 점은, 부분 염기서열의 문자들이 원래 염기서열에서 순서대로 나타나야 한다는 것이다. 예를 들면, "AC"는 C가 A다음에 오지 않기 때문에 "AGCT"의 부분 염기서열이 아니다.

이와 같은 부분 염기서열들 중에서 m(1 ≤ m ≤ n)번 이상 나타나는 부분 염기서열이 있다. 예를 들어 "AGAG"가 있을 때, "AG"와 "A"는 각각 두 번씩 나타나는 부분 염기서열이다. 이와 같이 m번 이상 나타나는 부분 염기서열들의 개수와, K번째의 부분 염기서열을 알고자 한다. 염기 서열들의 순서는, 길이가 짧은 것이 더 앞에 오며, 같은 길이일 때는 사전 식으로 앞서는 것이 앞에 온다.

입력

첫째 줄에 세 정수 n, m, K가 주어진다. 다음 줄에는 염기서열이 주어진다. K는 가능한 개수를 넘지 않는다.

출력

첫째 줄에 m번 이상 나타나는 부분 염기서열의 개수를 출력한다. 다음 줄에 K번째의 부분 염기서열을 출력한다.

예제 입력 1

48 4 11
GGCATTAGGATCGATCGGGTTATCGACAGCTAGTCTTCTCGAGGATCG

예제 출력 1

13
ATC

힌트

참고적으로 4번 이상 나타나는 부분 염기서열들을 A, C, G, T, GG, AT, AG, GA, TC, CG, ATC, TCG, ATCG 이다. 순서대로 나열한 것은 아니다.

출처

  • 문제의 오타를 찾은 사람: degurii