Description

Cirno 有一个字符串 $\texttt{S}$，并希望你能求出 $\texttt{S}$ 出现次数最多的非空子串的出现次数，记作 $p$。

Input Format

一行，一个字符串 $\texttt{S}$。

Output Format

一行，一个整数 $p$。

abababab

4

Hint

数据范围与约定

对于 $100\%$ 的数据保证: $0< |\texttt{S}| \le 10^7$，$\texttt{S}_x\in[\texttt{a},\texttt{z}]$。

子任务「本题采用捆绑测试」

• Subtask1（$40\%$）：$|\texttt{S}| \le 100$。
• Subtask2（$40\%$）：$|\texttt{S}| \le 10^5$。
• Subtask3（$20\%$）：无特殊限制。

名词解释

• 子串：字符串中任意个连续的字符组成的子序列称为该串的子串。