우편 구역 다양성

문제

우체국에 소포 N개가 접수된 순서대로 쌓여 있다. 각 소포에는 5자리 숫자로 된 우편번호가 붙어 있으며, 00123처럼 앞자리가 0일 수도 있다. 우편번호가 서로 같은 소포는 같은 구역으로 가는 소포이다. 배달원은 한 번에 접수 순서상 연속한 소포 K개를 묶어서 가방에 담는다. 묶음은 1번째부터 K번째, 2번째부터 K+1번째, …, N-K+1번째부터 N번째까지 총 N-K+1가지가 가능하다. 우체국장은 가방에 담긴 소포의 서로 다른 우편번호 수를 그 묶음의 다양성이라고 정의한다. 다양성이 가장 큰 묶음을 찾아 보고하려 한다. 가능한 모든 묶음 중 다양성의 최댓값, 그 최댓값을 가지는 묶음 중 시작 번호가 가장 작은 것의 시작 번호(1부터 센다), 그리고 최댓값을 가지는 묶음의 개수를 한 줄에 공백으로 구분해 출력하시오. 우편번호는 숫자가 아니라 5글자 문자열로 취급해도 되며, 앞자리 0까지 포함해 글자가 완전히 같을 때만 같은 우편번호이다.

입력

첫 줄에 N과 K가 주어진다. (1 ≤ K ≤ N ≤ 50,000) 둘째 줄에 N개의 우편번호가 접수 순서대로 공백으로 구분되어 주어진다. 각 우편번호는 00000 이상 99999 이하의 5자리 숫자이다.

출력

다양성의 최댓값, 그 최댓값을 가지는 가장 앞선 묶음의 시작 번호, 최댓값을 가지는 묶음의 개수를 공백으로 구분해 한 줄에 출력한다.

7 3
12345 12345 54321 11111 11111 11111 54321

3 2 1

4 2
00100 00200 00100 00200

2 1 3

출처: Devin.KR 자체 제작