At least some sleep
Limits: 1 sec., 512 MiB
This statement was translated automatically from Ukrainian.
Zenyk has a string \(s\) consisting of lowercase Latin letters. He decided that for each substring of this string, he needs to count how many times it is present in the string \(s\), and determine how many substrings are present the maximum number of times. The string is very large, so for the fourth night already, Zenyk does not close his eyes and stubbornly counts the number of occurrences of substrings in his string.
Marichka is very worried that Zenyk is not sleeping at all and decided to write a program that will instantly find the answer to the question that troubles Zenyk so much. Since you write programs much better than Marichka, the girl asks you for help: given a string, find how many of its substrings occur in it the maximum number of times.
Input
The only line contains the string \(s\).
Output
A single number — the number of substrings of string \(s\) that have the maximum number of repetitions in it.
Constraints
\(1 \le |s| \le 10^6\),
\(s\) contains only lowercase Latin letters.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| abcd | 10 |
| Input (stdin) | Output (stdout) |
|---|---|
| abab | 3 |
| Input (stdin) | Output (stdout) |
|---|---|
| aaabb | 1 |
Notes
In the first test, all substrings are unique, meaning they are present once.
In the second test, the substrings a, b,
and ab have two repetitions each.
In the third test, the substring a has the most
repetitions (three).
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|