시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB123362739.706%

문제

이 문제는 재미있습니다. 제가 좋아하는 문자열 퀴즈 같아요. 길이 $N$인 문자열 $S$와 양의 정수 $K$가 주어집니다. 길이 $K$ 이상인 팰린드롬을 부분 문자열(substring)로 가지는 문자열을 "영우 문자열"로 정의할 때, $S$의 서로 다른 부분 문자열 중에서 영우 문자열의 개수는 모두 몇 개일까요?

팰린드롬은 "기러기", "토마토", "스위스", "인도인", "별똥별", "우영우"와 같이 거꾸로 읽어도 같은 문자열을 의미하고 부분 문자열은 빈 문자열이 아닌, 문자열의 연속된 일부분을 의미합니다.

예를 들어, $S$가 "banana"이면서 $K=3$인 경우 $S$의 서로 다른 부분 문자열은

  • "a"
  • "an"
  • "ana"
  • "anan"
  • "anana"
  • "b"
  • "ba"
  • "ban"
  • "bana"
  • "banan"
  • "banana"
  • "n"
  • "na"
  • "nan"
  • "nana"

이고, 이 중에서 영우 문자열은

  • "ana"
  • "anan"
  • "anana"
  • "bana"
  • "banan"
  • "banana"
  • "nan"
  • "nana"

입니다.

입력

첫째 줄에 $S$의 길이 $N$과 양의 정수 $K$가 공백을 사이에 두고 차례로 주어집니다. $\left(1\leq K\leq N\leq 505\,505\right)$

둘째 줄에 영어 소문자로만 이루어진 문자열 $S$가 주어집니다.

출력

첫째 줄에 $S$의 서로 다른 부분 문자열 중에서 영우 문자열의 개수를 출력합니다.

예제 입력 1

6 3
banana

예제 출력 1

8

노트

개수에만 초점을 맞추면 문제를 풀 수 없습니다. 핵심을 봐야 돼요.