페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8178
서브태스크

moo패턴 문자열 1초 1024MB

문제

데이빗은 소문자로 이루어진 문자열에서 'moo' 패턴의 부분 문자열의 개수가 F개 이상 발견되면 기분이 좋아진다. 어느날 친구 엘시가 그 소식을 듣고 데이빗에게 길이가 N인 소문자로 이루어진 문자열을 읽어 주었다.

데이빗은 엘시가 읽어주는 문자열을 열심히 받아적었다. 데이빗은 받아쓰기 실력이 좋지 않기 때문에 문자 하나 정도는 실수로 잘못 적었을 수도 있다.

  • 'moo' 패턴의 문자열은 일반적으로 문자 c_i와 다른 문자 c_j가 c_ic_jc_j와 같은 형태로 있는 문자열로 정의된다.

    • 이 때, c_i는 소문자이고 c_j는 c_i 바로 뒤에 두 번 연속으로 나타나는 다른 소문자로, c_i ≠ c_j이다.

문자 하나 정도는 잘못 받아적었을 가능성을 고려하여 엘시가 읽어준 문자열에서 F개 이상 발견할 수 있는 모든 가능한 'moo' 패턴을 출력하는 프로그램을 작성하되, 알파벳 순으로 정렬된 결과를 출력해야 한다.


입력

첫 번째 줄에는 두 정수 N과 F가 주어진다. (3 ≤ N ≤ 20,000; 1 ≤ F ≤ N)

두 번째 줄에는 길이가 N인 소문자 문자열이 주어진다.


출력

가능한 'moo'패턴 부분 문자열의 수와 그 목록을 알파벳 순으로 출력한다. 각 'moo'패턴 부분 문자열은 한 줄에 하나씩 출력된다.


부분문제

번호 점수 조건
#130점

N \le 100

#270점

추가 제약 조건 없음


예제1

입력
102
zzmoozzmoo
출력
1
moo

어떤 문자를 바꾸어도 답은 달라지지 않는다.


예제2

입력
172
momoobaaaaaqqqcqq
출력
3
aqq
baa
cqq

8번 인덱스에 있는 문자 a의 원본은 b일 수 있고, 그 경우 부분 문자열 "baa"가 두 번 만들어진다.

11번 인덱스에 있는q의 원본은 c일 수 있고, 그 경우 부분 문자열 "cqq"가 두 번 만들어진다.

14번 인덱스에 있는c의 원본은 a일 수 있고, 그 경우 부분 문자열 "aqq"가 두 번 만들어진다.

이와 같이 새로운 'moo' 패턴을 만들 수 있다.


예제3

입력
31
ooo
출력
25
aoo
boo
coo
doo
eoo
foo
goo
hoo
ioo
joo
koo
loo
moo
noo
poo
qoo
roo
soo
too
uoo
voo
woo
xoo
yoo
zoo

출처

USACO 2024 December Bronze

역링크