Problem Description

Cirno has a string $\texttt{S}$, and wants you to find the maximum number of occurrences among all non-empty substrings of $\texttt{S}$. Denote this number as $p$.

Input Format

One line, a string $\texttt{S}$.

Output Format

One line, an integer $p$.

abababab

4

Hint

Constraints and Notes

For $100\%$ of the testdata, it is guaranteed that: $0 < |\texttt{S}| \le 10^7$, and $\texttt{S}_x \in [\texttt{a},\texttt{z}]$.

Subtasks (this problem uses bundled tests)

• Subtask 1 ($40\%$): $|\texttt{S}| \le 100$.
• Subtask 2 ($40\%$): $|\texttt{S}| \le 10^5$.
• Subtask 3 ($20\%$): no special constraints.

Glossary

• Substring: A subsequence consisting of any number of consecutive characters in a string is called a substring of that string.

Translated by ChatGPT 5