← 返回题目列表

Codeforces · 385/B

B. 熊和弦

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

熊有一个字符串 s = s1s2... s|s| (记录|s|为字符串长度),由小写英文字母组成。 bear 想要计算这样的索引对 i, j (1 ≤ i ≤ j ≤ |s|) 的数量,即字符串 x(i, j) = sisi + 1... sj 至少包含一个字符串“bear”作为子字符串。

字符串 x(i, j) 包含字符串“bear”,如果存在索引 k (i ≤ k ≤ j - 3),则 sk = b, sk + 1 = e, sk + 2 = a, sk + 3 = r。

帮助熊解决给定的问题。

输入

第一行包含一个非空字符串 s (1 ≤ |s| ≤ 5000)。保证字符串仅由小写英文字母组成。

输出

打印一个数字——问题的答案。

示例

输入 #1

bearbtear

输出 #1

6

输入 #2

bearaabearc

输出 #2

20

注意

在第一个示例中,以下对 (i, j) 匹配:(1, 4)、(1, 5)、(1, 6)、(1, 7)、(1, 8)、(1, 9)。

在第二个示例中,以下对 (i, j) 匹配:(1, 4)、(1, 5)、(1, 6)、(1, 7)、(1, 8)、(1, 9)、(1, 10)、(1, 11)、(2, 10)、(2, 11)、(3, 10)、(3, 11)、 (4, 10), (4, 11), (5, 10), (5, 11), (6, 10), (6, 11), (7, 10), (7, 11)。