#CODEFORCESP5672. Bear and Strings

    ID: 1083 远端评测题 1000ms 256MiB 尝试: 47 已通过: 8 难度: 8 上传者: 标签>brute forcegreedyimplementationmathstrings*1200

Bear and Strings

Bear and Strings

题面翻译

给定一个字符串,找出所有的子串 sisi+1...sj\ s_{i}s_{i+1}...s_{j},该子串包含  bear\ bear这个单词,输出满足条件的子串个数。

题目描述

The bear has a string s=s1s2... ss s=s_{1}s_{2}...\ s_{|s|} (record s |s| is the string's length), consisting of lowercase English letters. The bear wants to count the number of such pairs of indices i,j i,j (1<=i<=j<=s) (1<=i<=j<=|s|) , that string x(i,j)=sisi+1... sj x(i,j)=s_{i}s_{i+1}...\ s_{j} contains at least one string "bear" as a substring.

String x(i,j) x(i,j) contains string "bear", if there is such index k k (i<=k<=j3) (i<=k<=j-3) , that sk=b s_{k}=b , sk+1=e s_{k+1}=e , sk+2=a s_{k+2}=a , sk+3=r s_{k+3}=r .

Help the bear cope with the given problem.

输入格式

The first line contains a non-empty string s s (1<=s<=5000) (1<=|s|<=5000) . It is guaranteed that the string only consists of lowercase English letters.

输出格式

Print a single number — the answer to the problem.

样例 #1

样例输入 #1

bearbtear

样例输出 #1

6

样例 #2

样例输入 #2

bearaabearc

样例输出 #2

20

提示

In the first sample, the following pairs (i,j) (i,j) match: (1,4),(1,5),(1,6),(1,7),(1,8),(1,9) (1,4),(1,5),(1,6),(1,7),(1,8),(1,9) .

In the second sample, the following pairs (i,j) (i,j) match: $ (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) $ .