Codeforces 385(#226 Div2 only) B. Bear and Strings

問題

文字列sが与えられる。
文字列sのi文字目からj文字目を抜き出したものをs(i, j)とする。
s(i, j)のうち"bear"を連続する部分文字列として含むものはいくつあるか答えよ。

制約条件

sの長さ≦5000

方針

sの始点iは全通りためす。
jを右に動かしていて、何文字一致したかのカウントを増やしていって、一旦4文字一致したらそれ以降のjは全部有効。

みたいな感じでやったらオートマトンの作り方を間違えてbeabearみたいなのでマッチしないとかやってしまって闇。

ソースコード

string s;

int main(){
	cin >> s;
	
	int ans = 0;
	int n = s.size();
	
	rep(i, n){
		int cnt = 0;
		bool ok = 0;
		for(int j = i; j < n; j++){
			
			if(s[j] == "bear"[cnt]) cnt++;
			else{
				cnt = 0;
				if(s[j] == 'b') cnt++;
			}
			if(cnt >= 4) ok = 1;
			
			if(ok) ans++;
		}
	}
	cout << ans << endl;
	return 0;
}