AT_kupc2016_g.試験

你即将参加京都大学的入学考试。为了应对即将到来的试题，你决定记忆可能被考到的一组字符串集合 $S$。但是，直接记住 $S$ 过于繁琐，因此你选择记一个辅助字符串 $T$ 并确保 $S$ 和 $T$ 满足以下条件：

• 集合 $S$ 中的每个字符串都是 $T$ 的连续子串。
• 对于集合 $S$ 中的任意两个不同字符串 $x$ 和 $y$，$x$ 不能是 $y$ 的子序列。

注意，这里的连续子串指的是字母在 $T$ 中连续出现，而子序列则不要求连续。

在考试当天，当你打开试卷时，发现如果能回忆起集合 $S$ 就能取得满分。然而，你忘记了如何从字符串 $T$ 中恢复出集合 $S$。不过你仍然记得上述条件，因此你决定首先求出集合 $S$ 可能包含的最大元素数量。

输入由一行字符串 $T$ 组成。

输出集合 $S$ 的最大可能元素数量。

• 字符串长度 $1 \leq |T| \leq 10^5$
• 字符串 $T$ 仅由小写字母组成

部分得分

• 当 $1 \leq |T| \leq 50$ 时，若所有测试用例都回答正确，可获得 30 分。
• 当 $1 \leq |T| \leq 10^3$ 时，若所有测试用例都回答正确，可获得额外 30 分。

示例解释

在这个例子中，ab、ca 和 bc 是一种可能的最优复原方案。

本翻译由 AI 自动生成