시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 123 | 36 | 27 | 39.706% |
이 문제는 재미있습니다. 제가 좋아하는 문자열 퀴즈 같아요. 길이 $N$인 문자열 $S$와 양의 정수 $K$가 주어집니다. 길이 $K$ 이상인 팰린드롬을 부분 문자열(substring)로 가지는 문자열을 "영우 문자열"로 정의할 때, $S$의 서로 다른 부분 문자열 중에서 영우 문자열의 개수는 모두 몇 개일까요?
팰린드롬은 "기러기", "토마토", "스위스", "인도인", "별똥별", "우영우"와 같이 거꾸로 읽어도 같은 문자열을 의미하고 부분 문자열은 빈 문자열이 아닌, 문자열의 연속된 일부분을 의미합니다.
예를 들어, $S$가 "banana"이면서 $K=3$인 경우 $S$의 서로 다른 부분 문자열은
이고, 이 중에서 영우 문자열은
입니다.
첫째 줄에 $S$의 길이 $N$과 양의 정수 $K$가 공백을 사이에 두고 차례로 주어집니다. $\left(1\leq K\leq N\leq 505\,505\right)$
둘째 줄에 영어 소문자로만 이루어진 문자열 $S$가 주어집니다.
첫째 줄에 $S$의 서로 다른 부분 문자열 중에서 영우 문자열의 개수를 출력합니다.
6 3 banana
8
개수에만 초점을 맞추면 문제를 풀 수 없습니다. 핵심을 봐야 돼요.
University > 신촌지역 대학생 프로그래밍 대회 동아리 연합 > 2022 신촌지역 대학생 프로그래밍 대회 동아리 연합 여름 대회 (SUAPC 2022 Summer) H번