25564번 - 역삼역

문제

이 문제는 재미있습니다. 제가 좋아하는 문자열 퀴즈 같아요. 길이 $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$의 서로 다른 부분 문자열 중에서 영우 문자열의 개수를 출력합니다.

제한

노트

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