← 返回题目列表

Codeforces · 1817/F

F. 纠缠子串

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

给你一个字符串 $$$s$$$。如果有一个(可能是空的)链接字符串 $$$c$$$ 满足以下条件,则其一对非空子字符串 $$$(a, b)$$$ 被称为纠缠:

- $$$s$$$ 中每次出现 $$$a$$$ 后紧跟着 $$$cb$$$;
- $$$s$$$ 中每次出现 $$$b$$$ 之前都紧接着 $$$ac$$$。

换句话说,$$$a$$$ 和 $$$b$$$ 仅作为 $$$acb$$$ 的子字符串出现在 $$$s$$$ 中。计算 $$$s$$$ 的纠缠子串对总数。

字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。

输入

第一行也是唯一一行包含小写英文字母的字符串 $$$s$$$ ($$$1 \leq |s| \leq 10^5$$$) — 您应该计算纠缠子字符串对的字符串。

输出

输出单个整数,$$$s$$$ 的纠缠子串对的数量。

示例

输入 #1

abba

输出 #1

1

输入 #2

abacaba

输出 #2

0

输入 #3

abcabcabcabc

输出 #3

5

输入#4

adamant

输出#4

82

注意

在第一个示例中,唯一的纠缠对是 (ab,ba)。对于这一对,相应的链接字符串 $$$c$$$ 为空,因为它们仅作为整个字符串 abba 的子字符串出现,而整个字符串 abba 之间没有任何字符。

在第二个示例中,没有纠缠对。

在第三个示例中,纠缠对是 (a,b)、(b,c)、(a,c)、(a,bc) 和 (ab,c)。对于大多数对,相应的链接字符串 $$$c$$$ 为空,但对 (a,c) 除外,其链接字符串 $$$c$$$ 为 b,因为 a 和 c 仅作为字符串 abc 的子字符串出现。