385B.md (1642B)
1 Source: https://codeforces.com/problemset/problem/385/B 2 3 B. Bear and Strings 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 The bear has a string *s* = *s*1*s*2... *s*|*s*| (record |*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* (1 ≤ *i* ≤ *j* ≤ |*s*|), that string *x*(*i*, *j*) = *s**i**s**i* + 1... *s**j* contains at least one string "bear" as a substring. 22 23 String *x*(*i*, *j*) contains string "bear", if there is such index *k* (*i* ≤ *k* ≤ *j* - 3), that *s**k* = *b*, *s**k* + 1 = *e*, *s**k* + 2 = *a*, *s**k* + 3 = *r*. 24 25 Help the bear cope with the given problem. 26 27 Input 28 29 The first line contains a non-empty string *s* (1 ≤ |*s*| ≤ 5000). It is guaranteed that the string only consists of lowercase English letters. 30 31 Output 32 33 Print a single number — the answer to the problem. 34 35 Examples 36 37 Input 38 39 ``` 40 bearbtear 41 ``` 42 43 Output 44 45 ``` 46 6 47 ``` 48 49 Input 50 51 ``` 52 bearaabearc 53 ``` 54 55 Output 56 57 ``` 58 20 59 ``` 60 61 Note 62 63 In the first sample, the following pairs (*i*, *j*) match: (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9). 64 65 In the second sample, the following pairs (*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).