반복된 주차 구역 기록

문제

한 주차장에서는 입차한 차량이 어느 구역에 배정되었는지를 순서대로 기록한다. 구역 이름은 영어 소문자 하나이며, 차량 한 대가 배정될 때마다 해당 구역의 이름을 기록 끝에 덧붙인다. 같은 구역에는 여러 차량을 배정할 수 있으므로 같은 문자가 여러 번 나타날 수 있다. 이 기록은 차량의 입차 순서를 나타내며, 차량이 출차한 시각이나 현재 남아 있는 차량 수는 나타내지 않는다. 관리인은 연속한 K대의 구역 배정 순서가 얼마나 다양하게 나타났는지 조사하려고 한다. 기록에서 시작 위치 하나를 정한 뒤 그 위치부터 정확히 K개의 문자를 읽은 문자열을 배정 무늬라고 부른다. 마지막 문자까지 K개를 읽을 수 있는 시작 위치만 사용한다. 전체 기록의 길이가 N이면 사용할 시작 위치는 1부터 N-K+1까지이며, 각 시작 위치에서 배정 무늬가 한 번 발생한 것으로 센다. 두 배정 무늬는 같은 위치의 문자가 모두 같을 때에만 같은 종류이다. 같은 구역들을 포함하더라도 순서가 다르면 다른 종류이다. 서로 다른 시작 위치에서 얻은 무늬는 기록의 일부를 공유해도 각각 별도로 발생한 것으로 센다. 예를 들어 기록이 'aaaa'이고 K가 3이면 첫 번째 위치와 두 번째 위치에서 모두 'aaa'가 발생하므로, 이 무늬의 발생 횟수는 2이다. 관리인이 필요한 값은 전체 배정 무늬의 종류 수와 그중 두 번 이상 발생한 종류 수이다. 하나의 무늬가 여러 번 발생해도 종류 수에는 한 번만 포함한다. 두 번 이상 발생한 종류 수 역시 발생 횟수의 합이 아니라 조건을 만족하는 서로 다른 무늬의 개수이다. 기록의 처음과 끝을 이어 붙여 무늬를 만들지는 않는다. 적어도 하나의 배정 무늬가 존재하도록 K는 N 이하로 주어지며, 반복된 종류가 하나도 없으면 두 번째 값은 0이다.

입력

첫째 줄에 정수 N과 K가 공백으로 주어진다. 1 ≤ N ≤ 200,000, 1 ≤ K ≤ min(10, N)이다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S는 영어 소문자로만 이루어져 있으며, 왼쪽부터 입차한 차량의 배정 구역을 나타낸다.

출력

배정 무늬의 전체 종류 수와 두 번 이상 발생한 종류 수를 공백으로 구분하여 한 줄에 정수로 출력한다. 두 번 이상 발생한 종류가 없으면 두 번째 값으로 0을 출력한다.

8 2
abacabab

4 2

4 3
aaaa

1 1

5 5
abcde

1 0

출처: Devin.KR 자체 제작