← 返回题目列表

AtCoder · abc428_b

D. 最常见的子字符串

中文机器翻译题面 查看原题

分数: 200 点

问题陈述

给你一个字符串 S 长度 N 由小写英文字母组成。

定义 出现次数 字符串的 一个字符串的 t 长度 K 作为整数的数量 i 满足以下条件:

  • 1 \leq i \leq N-K+1
  • 的子串 S 来自 i- 第一个字符 (i+K-1)- 第一个字符匹配 t.

查找最大值 x 长度的字符串出现的次数 K。 另外,输出所有长度的字符串 K 与 x 按字典升序出现。

约束

  • N, K 是整数。
  • S 是一个长度为的字符串 N 由小写英文字母组成。
  • 1 \leq K \leq N \leq 100

输入

输入由标准输入按以下格式给出:

N K
S

输出

输出两行。

第一行应包含最大值 x 长度的字符串出现的次数 K.

第二行应包含所有长度的字符串 K 与 x 按字典升序出现,用空格分隔。


示例输入 1

9 3
ovowowovo

示例输出 1

2
ovo owo

以下字符串出现两次:

  • 对于字符串 ovo, i=1,7 满足条件,因此出现的次数 ovo is 2.
  • 对于字符串 owo, i=3,5 满足条件,因此出现的次数 owo is 2.

没有长度的字符串 3 出现两次以上,因此最大值为 2.

另一方面,以下是出现次数少于两次的字符串示例:

  • 对于字符串 vow, i=2 满足条件,因此出现的次数 vow is 1.
  • 对于字符串 ooo,没有 i 满足条件,因此出现的次数 ooo is 0.

示例输入 2

9 1
ovowowovo

示例输出 2

5
o

示例输入 3

35 3
thequickbrownfoxjumpsoverthelazydog

示例输出 3

2
the