Contact

시간 제한1초메모리 제한128 MB

요약

이진 문자열과 길이 범위 [A,B]가 주어질 때, 가장 많이 나타난 N개의 빈도와 각 빈도를 이루는 패턴을 정해진 순서 규칙에 따라 보고한다.

난이도: 어려움10점 중 9점
유형: 문자열, 정렬, 해시맵, 문자열 매칭
정답자: 아직 제출이 없습니다

문제

Astro Insky 박사는 전파망원경 센터에서 일한다. 최근 그녀는 은하 중심에서 곧바로 전송되는 매우 흥미로운 마이크로파 펄스 신호를 발견했다. 이 신호는 외계 지적 생명체가 보낸 것일까, 아니면 그저 별들의 평범한 맥동에 지나지 않는 것일까?

Insky 박사가 진실을 밝힐 수 있도록, 그녀가 기록한 파일 속 비트 패턴을 분석하는 도구를 만들어 주어야 한다. 박사는 매일의 데이터 파일에서 길이가 $A$ 이상 $B$ 이하인 패턴 중 가장 자주 반복되는 것들을 찾고자 한다. 각 경우에 대해 가장 큰 $N$ 개의 서로 다른 빈도(즉, 등장 횟수)를 구한다. 패턴의 등장은 서로 겹칠 수 있으며, 최소 한 번 이상 등장하는 패턴만 고려한다.

입력

첫째 줄: 패턴의 최소 길이를 나타내는 정수 $A$
둘째 줄: 패턴의 최대 길이를 나타내는 정수 $B$
셋째 줄: 보고할 서로 다른 빈도의 개수를 나타내는 정수 $N$
넷째 줄: 0과 1로 이루어진 문자열이며, 문자 2로 끝난다.

출력

표준 출력으로 최대 $N$ 개의 줄로 이루어진 보고서를 출력한다. 가장 큰 빈도부터 차례로, 최대 $N$ 개의 빈도와 그에 해당하는 패턴들을 나열한다. 줄은 빈도가 큰 순서대로 정렬한다. 각 줄은 빈도 패턴 패턴 ... 패턴 형식이며, 여기서 빈도는 뒤따르는 패턴들의 등장 횟수이다. 한 줄 안에서 패턴은 길이가 긴 순서대로 나열하고, 길이가 같은 패턴들은 이진수 값이 큰 순서(역순)로 나열한다. 서로 다른 빈도가 $N$ 개보다 적으면 출력 줄 수도 $N$ 보다 적어진다.

제한

$0 < N \le 20$
$0 < A \le B \le 20$

예제1

예제 1

입력

2
4
10
010100100100010001111011000010100110011110000100100111100100000002

예상 출력

23 00
15 10 01
12 100
11 001 000 11
10 010
8 0100
7 1001 0010
6 0000 111
5 1000 110 011
4 1100 0011 0001