B - Most Frequent Substrings Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

英小文字からなる長さ N の文字列 S が与えられます。

長さ K の文字列 t の出現回数を、以下を満たす整数 i の個数として定義します。

  • 1 \leq i \leq N-K+1
  • S の i 文字目から i+K-1 文字目までからなる部分文字列が t に一致する。

長さ K の文字列に対する出現回数の最大値 x を求めてください。 また、出現回数が x となるような長さ K の文字列をすべて辞書順昇順に出力してください。

制約

  • N, K は整数
  • S は英小文字からなる長さ N の文字列
  • 1 \leq K \leq N \leq 100

入力

入力は以下の形式で標準入力から与えられる。

N K
S

出力

2 行出力せよ。

1 行目には、長さ K の文字列に対する出現回数の最大値 x を出力せよ。

2 行目には、出現回数が x となるような長さ K の文字列を辞書順昇順に、空白区切りで出力せよ。

入力例 1

9 3
ovowowovo

出力例 1

2
ovo owo

出現回数 2 の文字列として、以下が挙げられます。

  • 文字列 ovo について、i=1,7 が条件を満たすことから、ovo の出現回数は 2 です。
  • 文字列 owo について、i=3,5 が条件を満たすことから、owo の出現回数は 2 です。

出現回数が 2 よりも大きいような長さ 3 の文字列は存在しないので、求める最大値は 2 です。

一方で、出現回数が 2 よりも小さい文字列として、以下が挙げられます。

  • 文字列 vow について、i=2 が条件を満たすことから、vow の出現回数は 1 です。
  • 文字列 ooo について、条件を満たす i が存在しないことから、ooo の出現回数は 0 です。

入力例 2

9 1
ovowowovo

出力例 2

5
o

入力例 3

35 3
thequickbrownfoxjumpsoverthelazydog

出力例 3

2
the

Score : 200 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters.

Define the number of occurrences of a string t of length K as the number of integers i that satisfy the following condition:

  • 1 \leq i \leq N-K+1
  • The substring of S from the i-th character to the (i+K-1)-th character matches t.

Find the maximum value x of the number of occurrences of a string of length K. Also, output all strings of length K with x occurrences in ascending lexicographical order.

Constraints

  • N, K are integers.
  • S is a string of length N consisting of lowercase English letters.
  • 1 \leq K \leq N \leq 100

Input

The input is given from Standard Input in the following format:

N K
S

Output

Output two lines.

The first line should contain the maximum value x of the number of occurrences of a string of length K.

The second line should contain all strings of length K with x occurrences in ascending lexicographical order, separated by spaces.

Sample Input 1

9 3
ovowowovo

Sample Output 1

2
ovo owo

The following strings have two occurrences:

  • For the string ovo, i=1,7 satisfy the condition, so the number of occurrences of ovo is 2.
  • For the string owo, i=3,5 satisfy the condition, so the number of occurrences of owo is 2.

There is no string of length 3 with more than two occurrences, so the maximum value is 2.

On the other hand, the following are examples of strings with fewer than two occurrences:

  • For the string vow, i=2 satisfies the condition, so the number of occurrences of vow is 1.
  • For the string ooo, there is no i that satisfies the condition, so the number of occurrences of ooo is 0.

Sample Input 2

9 1
ovowowovo

Sample Output 2

5
o

Sample Input 3

35 3
thequickbrownfoxjumpsoverthelazydog

Sample Output 3

2
the