#PU1445. USACO 2024 December Contest, Bronze — Problem 3. It's Mooin' Time

    ID: 1297 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 普及 上传者: 标签>USACO赛事:dec24来源:usaco.orgscoring:equal_test_cases后缀数组字典树

USACO 2024 December Contest, Bronze — Problem 3. It's Mooin' Time

USACO 2024 December Contest, Bronze — Problem 3. It's Mooin' Time

题目描述

Farmer John is trying to describe his favorite USACO contest to Elsie, but she is having trouble understanding why he likes it so much. He says "My favorite part of the contest was when Bessie said 'It's Mooin' Time' and mooed all over the contest." Elsie still doesn't understand so Farmer John downloads the contest as a text file and tries to explain what he means. The contest is defined as a string of lowercase letters of length NN (3≤N≤20 0003 \leq N \leq 20\,000). A moo is generally defined as the substring cicjcjc_ic_jc_j where some character cic_i followed directly by 22 occurrences of some character cjc_j where ci≠cjc_i \neq c_j. According to Farmer John, Bessie moos a lot, so if some moo appears at least FF (1≤F≤N1\le F\le N) times in the contest, that might be from Bessie. However, Farmer John's download might have been corrupted, and the text file might have up to one character that differs from the original file. Print all possible moos that Bessie could have made taking the potential error into account, sorted in alphabetical order.

输入格式

The first line contains NN and FF, representing the length of the string and the frequency threshold for a moo by Bessie. The second line contains a string of lowercase letters of length NN, representing the contest.

输出格式

Print out the number of possible moos that Bessie makes, followed by a lexicographically sorted list of the moos. Each moo should appear on a separate line.

数据范围

Inputs 4-8: N≤100N \le 100 Inputs 9-13: No additional constraints. Problem credits: Suhas Nagar

样例

样例 1

10 2
zzmoozzmoo
1
moo
In this case, no character change affects the answer. The only moo Bessie made
was "moo".

样例 2

17 2
momoobaaaaaqqqcqq
3
aqq
baa
cqq
In this case, the $a$ at position $8$ (zero-indexed) could have been corrupted from a $b$ which
would have resulted in "baa" being a moo that Bessie made twice. Alternatively,
the $q$ at position $11$ could have been corrupted from a $c$ which would have
resulted in "cqq" being a possible moo that Bessie made. "aqq" can be made by
swapping the $c$ with an $a$.

样例 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