ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#8178
サブタスク

moo패턴 문자열 1s 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

10 2
zzmoozzmoo
1
moo

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


例題 #2

17 2
momoobaaaaaqqqcqq
3
aqq
baa
cqq

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

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

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

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


例題 #3

3 1
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

ログインしないとコードを書けません。