题目描述

给定字符串 $s$。

定义 $s(l,r)$ 为 $s$ 第 $l\sim r$ 个字符组成的字符串。

定义 $t(l,r)$ 为 $s$ 删除第 $l\sim r$ 个字符后得到的字符串。

找到最长的区间 $[l,r]$，使得 $s(l,r)$ 在 $t(l,r)$ 中作为子串出现。

输入格式

一行一个字符串 $s$。

输出格式

输出一个整数，表示最长可能的区间长度。

输入输出样例 #1

输入 #1

abcxyzabc

输出 #1

3

输入输出样例 #2

输入 #2

bbcdbcbbcbadadda

输出 #2

5

说明/提示

样例解释

不难注意到 $\texttt{bbcdbcb\underline{bcbad}adda} \to \texttt{bbcd\underline{bcbad}da}$。

数据范围

对于 $100\%$ 的数据，保证：

• $1\le |s| \le 10^5$；
• $s$ 中只有小写字母。