← 返回题目列表

Codeforces · 1789/F

F. 薮和脑力

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

薮猫喜欢脑力和他的脑力问题。

Serval 定义字符串 $$$T$$$ 是强大的,当且仅当 $$$T$$$ 可以通过多次连接某个字符串 $$$T'$$$ 来获得。正式地说,$$$T$$$ 是强大的,当且仅当存在一个字符串 $$$T'$$$ 和一个整数 $$$k\geq 2$$$ 使得 $$$$$$T=\underbrace{T'+T'+\dots+T'}_{k\text{ times}}$$$$$$

比如gogogo很强大,因为它可以通过连接3次go得到,但威力并不强大。

Serval 有一个由小写英文字母组成的字符串 $$$S$$$。他对 $$$S$$$ 的最长强大子序列感到好奇,他只需要你找出它的长度。如果 $$$S$$$ 的所有非空子序列都不强大,则答案被认为是 $$$0$$$。

如果 $$$a$$$ 可以通过删除几个(可能是零个或全部)字符从 $$$b$$$ 获得,则字符串 $$$a$$$ 是字符串 $$$b$$$ 的子序列。

输入

第一行包含一个由小写英文字母组成的字符串 $$$S$$$ ($$$|S|\leq 80$$$)。

输出

打印单个整数 — $$$S$$$ 的最长有效子序列的长度。如果 $$$S$$$ 的所有非空子序列都不强大,则打印 $$$0$$$。

示例

输入 #1

buaa

输出 #1

2

输入 #2

codeforcesround

输出 #2

6

输入 #3

oooooooooooaaaaeaaiaujooooooooooooo

输出 #3

24

输入#4

zero

输出#4

0

注意

对于第一个样本,buaa 的所有非空子序列如下:

- b
- 你
- a(出现两次,buaa和buaa)
- 布
- ba(出现两次,buaa 和 buaa)
- ua(出现两次,buaa 和 buaa)
- AA
- bua (出现两次, buaa 和 buaa )
- 咩
- uaa
- buaa

由于 $$$\texttt{aa} = \texttt{a} + \texttt{a}$$$,aa 是一个强大的子序列。可以证明aa是其中唯一强大的子序列。所以答案是$$$2$$$。

对于第二个样本,最长的强大子序列是来自 codeforcesround 的 cocoded。所以答案是$$$6$$$。