#P0274. 哞叫时间

    传统题 1000ms 256MiB 显示标签>USACOUSACO 2024 December Contest Bronze

哞叫时间

题目描述

农夫约翰正在试图向埃尔茜描述他最喜欢的 USACOUSACO 竞赛,但她很难理解为什么他这么喜欢它。

他说「竞赛中我最喜欢的部分是贝茜说 『现在是哞哞时间』并在整个竞赛中一直哞哞叫」。

埃尔茜仍然不理解,所以农夫约翰将竞赛以文本文件形式下载,并试图解释他的意思。

竞赛被定义为一个长度为 NN 的小写字母字符串。

一种哞叫一般地定义为子串 cicjcjc_ic_jc_j,其中某字符 cic_i 之后紧跟着 22 个某字符 cjc_j,且 cicjc_i≠c_j

根据农夫约翰的说法,贝茜哞叫了很多,所以如果某种哞叫在竞赛中出现了至少 FF 次,那可能就是贝茜发出的。

然而,农夫约翰的下载可能损坏,文本文件可能存在至多一个字符与原始文件不同。

将可能的误差考虑在内,输出所有可能是贝茜发出的哞叫,按字母顺序排序。

输入格式

输入的第一行包含 NNFF,表示字符串的长度以及贝茜的哞叫的频次下限。

第二行包含一个长度为 NN 的小写字母字符串,表示竞赛。

输出格式

输出可能是贝茜发出的哞叫的数量,以下是按字典序排序的哞叫列表。

每行输出一种哞叫。

数据范围

3N20000.3≤N≤20000. 1FN.1≤F≤N.

输入样例1:

10 2
zzmoozzmoo

输入样例1 :

1
moo

样例1解释

在这个样例中,任何字符变化都不会影响答案。

唯一贝茜可能发出的哞叫是 moo

输入样例2:

17 2
momoobaaaaaqqqcqq

输出样例2:

3
aqq
baa
cqq

样例2解释

在这个样例中,位置 88(从零开始索引)的 a 可能是由 b 损坏导致的,这使得 baa 成为一种贝茜发出两次的可能的哞叫。

此外,位置 11 的 q 可能是由 c 损坏导致的,这使得 cqq 成为一种贝茜可能的哞叫。

aqq 可以通过将 c 换成 a 来达到。

输入样例3:

3 1
ooo

输出样例3:

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