Most Frequent Substrings

AtCoder

IDabc428_b

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

9 3
ovowowovo

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$.

Input #2

9 1
ovowowovo

Output #2

5
o

Input #3

35 3
thequickbrownfoxjumpsoverthelazydog

Output #3

2
the

API Response (JSON)

{
  "problem": {
    "name": "Most Frequent Substrings",
    "description": {
      "content": "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 foll",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc428_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a string $S$ of length $N$ consisting of lowercase English letters.\nDefine the **number of occurrences** of a string $t$ of length $K$ as the number of integers $i$ that satisfy the foll...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments