← 返回题目列表

Codeforces · 1307/C

C. 牛和消息

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

奶牛贝西刚刚截获了农夫约翰发送给汉堡女王的短信!然而,贝西确信里面隐藏着秘密信息。

文本是小写拉丁字母的字符串$$$s$$$。如果 $$$t$$$ 作为索引形成算术级数的 $$$s$$$ 的子序列存在,她认为字符串 $$$t$$$ 隐藏在字符串 $$$s$$$ 中。例如,字符串 aab 隐藏在字符串 aaabb 中,因为它出现在索引 $$$1$$$、$$$3$$$ 和 $$$5$$$ 处,这些索引形成等差数列,公差为 $$$2$$$。贝西认为任何出现次数最多的隐藏字符串就是秘密消息。如果索引集不同,则 $$$S$$$ 子序列的两次出现是不同的。帮助她找出秘密信息出现的次数!

例如,字符串aaabb中,a被隐藏$$$3$$$次,b被隐藏$$$2$$$次,ab被隐藏$$$6$$$次,aa被隐藏$$$3$$$次,bb被隐藏$$$1$$$次,aab被隐藏$$$2$$$次,aaa被隐藏$$$1$$$次,abb被隐藏$$$1$$$ 次,aaab 被隐藏 $$$1$$$ 次,aabb 被隐藏 $$$1$$$ 次,aaabb 被隐藏 $$$1$$$ 次。秘密消息出现的次数为$$$6$$$。

输入

第一行包含一个由小写拉丁字母组成的字符串 $$$s$$$ ($$$1 \le |s| \le 10^5$$$) — Bessie 截获的文本。

输出

输出一个整数——秘密消息出现的次数。

示例

输入 #1

aaabb

输出 #1

6

输入 #2

usaco

输出 #2

1

输入 #3

lol

输出 #3

2

注意

在第一个示例中,这些是所有隐藏字符串及其索引集:

- a 出现在 $$$(1)$$$、$$$(2)$$$、$$$(3)$$$
- b 出现在 $$$(4)$$$、$$$(5)$$$
- ab 出现在 $$$(1,4)$$$、$$$(1,5)$$$、$$$(2,4)$$$、$$$(2,5)$$$、$$$(3,4)$$$、$$$(3,5)$$$
- aa 出现在 $$$(1,2)$$$、$$$(1,3)$$$、$$$(2,3)$$$
- bb 出现在 $$$(4,5)$$$
- aab 出现在 $$$(1,3,5)$$$, $$$(2,3,4)$$$
- aaa 出现在 $$$(1,2,3)$$$
- abb 出现在 $$$(3,4,5)$$$
- aaab 出现在 $$$(1,2,3,4)$$$
- aabb 出现在 $$$(2,3,4,5)$$$
- aaabb 出现在 $$$(1,2,3,4,5)$$$

在第二个示例中,隐藏字符串不会出现多次。

在第三个示例中,隐藏字符串是字母 l。