← 返回题目列表

AtCoder · kupc2016_g

G. 考试

中文机器翻译题面 查看原题

分数: 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