역삼역

이 문제는 재미있습니다. 제가 좋아하는 문자열 퀴즈 같아요. 길이 $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"

이 중 영우 문자열은 다음 8개입니다.

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

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

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

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

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