The bear has a string s?=?s1s2... 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)?=?sisi?+?1... sj contains at least one string "bear" as a substring.
String x(i,?j) contains string "bear", if there is such index k (i?≤?k?≤?j?-?3), that sk?=?b, sk?+?1?=?e, sk?+?2?=?a, sk?+?3?=?r.
Help the bear cope with the given problem.
The first line contains a non-empty string s (1?≤?|s|?≤?5000). It is guaranteed that the string only consists of lowercase English letters.
Print a single number — the answer to the problem.
bearbtear
6
bearaabearc
20
In the first sample, the following pairs (i,?j) match: (1,?4),?(1,?5),?(1,?6),?(1,?7),?(1,?8),?(1,?9).
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).
#include <iostream> #include <string> #include <stdio.h> #include <vector> #include <algorithm> using namespace std; int gao(string s){ vector< pair<int,int> >seg ; vector< pair<int,int> >::iterator it ; seg.clear() ; int i ,Len = s.length() ,L ,R ,ans = 0 ,reL ; for(i = 0 ; i <= Len - 4 ; i++){ if(s[i]==‘b‘&&s[i+1]==‘e‘&&s[i+2]==‘a‘&&s[i+3]==‘r‘) seg.push_back(make_pair(i+1,i+1+3)) ; } if(seg.size() == 0) return 0 ; it = seg.begin() ; reL = L = it->first ; R = it->second ; ans += L * (Len - R +1) ; for(it++; it != seg.end() ; it++){ L = it->first ; R = it->second ; ans += (L - reL) * (Len - R + 1) ; reL = L ; } return ans ; } int main(){ string s ; while(cin>>s){ cout<<gao(s)<<endl ; } return 0 ; }