팰린드롬 제거

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

요약

단어와 길이 M이 주어졌을 때, 길이가 M 이상인 회문 부분 문자열이 남지 않도록 깨뜨려야 하는 글자의 최소 개수를 구합니다.

문제

이안이는 팰린드롬을 싫어한다. 팰린드롬은 level, bob처럼 앞으로 읽어도 뒤로 읽어도 같은 단어이다. 이안이는 팰린드롬인 단어를 보면 당장 그 단어를 지워야 할 정도로 팰린드롬을 싫어한다.

이제 이안이는 팰린드롬이 아닌 단어라도 부분문자열 중 팰린드롬이 하나라도 있으면 그 단어를 지우고 싶어 한다. 하지만 그렇게 하면 남는 단어가 거의 없을 것이다. 그래서 글자 몇 개를 부숴 길이가 $M$ 이상인 팰린드롬 부분문자열이 없도록 만들려고 한다.

글자를 부수면 부서진 글자가 포함된 문자열은 팰린드롬이 될 수 없다. 예를 들어 abcba에서 가운데 c를 부수면 ab#ba가 되고, 이는 팰린드롬이 아니다.

banana의 부분문자열 중 anana, ana, nan은 팰린드롬이므로 글자를 부숴야 한다. $M = 2$ 인 경우 두 번째 a를 부수면 ban#na가 되어, 길이가 $2$ 이상인 팰린드롬 부분문자열이 없다.

첫 번째 줄에 단어의 길이 $N$ 과 싫어하는 팰린드롬의 길이 $M$ 이 공백으로 구분되어 주어진다.

두 번째 줄에 길이 $N$ 인 단어가 주어진다.

길이가 $M$ 이상인 팰린드롬 부분문자열이 없도록 만들기 위해 부숴야 하는 글자 개수의 최솟값을 출력한다.