제2종 드 브루인 수열

문자 0과 1로 이루어진 길이 $2^n + n - 1$의 단어 $s$가 있을 때, 길이가 $n$인 모든 이진 단어가 $s$의 부분 단어(연속된 문자들로 이루어진 조각)로 나타나면 $s$를 차수 $n$의 드 브루인 수열이라고 한다. 예를 들어 0001011100은 차수 3의 드 브루인 수열이다.

제2종 드 브루인 수열(type two de Bruijn sequence)이란, 길이가 $n$인 모든 이진 단어가 $s$의 부분 수열, 즉 반드시 연속일 필요는 없는 문자들의 조각으로 나타나는 임의의 길이의 단어 $s$를 말한다. 예를 들어 00101101은 차수 3의 제2종 드 브루인 수열이다. 알려진 바로는 니콜라스 호베르트 드 브루인(Nicolaas Govert de Bruijn)이 이런 수열을 고안한 것은 아니지만, 그 정의는 앞의 것과 분명히 닮아 있다.

0과 1로만 이루어진 단어 $s$가 주어진다. $s$가 차수 $n$의 제2종 드 브루인 수열이 되도록 하려면 $s$의 끝에 숫자(0 또는 1)를 최소 몇 개 덧붙여야 하는가?

첫째 줄에 두 정수 $m$과 $n$이 공백 하나로 구분되어 주어진다 ($1 \le m, n \le 10^6$). 둘째 줄에는 0과 1로만 이루어진 길이 $m$의 단어 $s$가 공백 없이 주어진다.

$s$가 차수 $n$의 제2종 드 브루인 수열이 되도록 하기 위해 $s$의 끝에 덧붙여야 하는 숫자의 최소 개수를, 음이 아닌 정수 하나로 출력한다.

$s =$ 00101이고 $n = 3$일 때, 두 문자 01을 덧붙이면 0010101이 되며 이는 차수 3의 제2종 드 브루인 수열이다. 따라서 답은 2이다.