음머의 시간

농부 존(Farmer John)은 엘시(Elsie)에게 자신이 가장 좋아하는 USACO 대회에 대해 설명하고 있지만, 엘시는 존이 왜 그렇게 그 대회를 좋아하는지 이해하지 못하고 있다. 존은 이렇게 말한다. "그 대회에서 내가 가장 좋아했던 부분은 베시(Bessie)가 '음머의 시간이다(It's Mooin' Time)'라고 말하고는 대회 내내 음머 하고 울었던 때야."

엘시가 여전히 이해하지 못하자, 농부 존은 그 대회를 텍스트 파일로 내려받아 자신이 무슨 뜻인지 설명하려 한다. 대회는 길이 \(N\) (\(3 \leq N \leq 20\,000\))의 소문자 문자열로 정의된다. 음머(moo)는 일반적으로 부분 문자열 \(c_ic_jc_j\)로 정의되는데, 어떤 문자 \(c_i\) 바로 뒤에 어떤 문자 \(c_j\)가 \(2\)번 연달아 나타나고 \(c_i \neq c_j\)인 경우이다. 농부 존에 따르면 베시는 음머를 아주 많이 하므로, 어떤 음머가 대회에서 \(F\)번 (\(1\le F\le N\)) 이상 나타난다면 그것은 베시가 한 것일 수 있다.

하지만 농부 존의 다운로드 과정에서 파일이 손상되었을 수 있어서, 텍스트 파일에는 원본 파일과 다른 문자가 최대 한 개 있을 수 있다. 이 잠재적 오류를 고려하여, 베시가 냈을 수 있는 모든 음머를 사전순으로 정렬하여 출력하시오.

문제 제공: Suhas Nagar

배점

• 입력 4-8: \(N \le 100\)
• 입력 9-13: 추가 제약이 없다.

문제 제공: Suhas Nagar

첫째 줄에 문자열의 길이 \(N\)과 베시의 음머로 판정하기 위한 빈도 기준 \(F\)가 주어진다.

둘째 줄에 대회를 나타내는 길이 \(N\)의 소문자 문자열이 주어진다.

베시가 냈을 수 있는 음머의 개수를 출력한 뒤, 그 음머들을 사전순으로 정렬한 목록을 출력한다. 각 음머는 별도의 줄에 출력해야 한다.

riseoj 작성

출처 올림피아드 > USACO > 2024-2025 > December > Bronze