分数: 200 点
问题陈述
明天你要参加京都大学入学考试 并决定记住一组字符串 S 预计会出现在考试中。 因为真的很难记 S 就这样, 你决定记住一个字符串 T 有效包含中的所有字符串 S.
您已确认以下条件 S 和 T 很满意。- 中的每个字符串 S 是 连续 子序列(1) in T .
- 对于每对字符串 x, y (x \neq y) in S , x 不是子序列(2) of y.
请注意,(1) 是“连续子序列”,而(2) 是“子序列”。
第二天,你在考试时打开了习题册 发现只有记住了才能得满分 S。 然而,你已经忘记了如何重建 S 来自 T 。 既然你只记得 T 满足上述条件, 首先你决定找到最大可能的元素数 S .
约束
- 1 \leq |T| \leq 10^5
- T 仅由小写字母组成。
部分积分 通过满足条件的测试集将获得
- 30 积分: 1 \leq |T| \leq 50 .
- 另一个 通过所有测试将获得 30 积分: 1 \leq |T| \leq 10^3.
输入
输入由标准输入按以下格式给出:
T
输入仅包含 T 一行。
输出
打印元素的最大数量S .
示例输入 1
abcabc
示例输出 1
3在这种情况下,
ab,ca 和 bc 是最佳答案的示例。
示例输入 2
abracadabra
示例输出 2
7
示例输入 3
abcbabbcabbc
示例输出 3
8
示例输入 4
bbcacbcbcabbabacccbbcacbaaababbacabaaccbccabcaabba
示例输出 4
44