torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces #226, B : Bear and Strings

概要

 文字列 s が与えられる。x( i, j ) = s_i + x_{ i + 1 } + \cdots + x_j が文字列 "bear" を含むような ( i, j ) の総数を求めよ。

解法

 i を決めたとき、"bear" が出現するまで j を進めるとします。このときの j より大きい j' による x( i, j' ) は全て "bear" を含みます。従って、このときの i に対応する有効な j の個数は |s| - j + 1 です。全ての i に対してこの工程を試して、結果の総和をとれば全体の答えが求まります。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	string s;
	cin >> s;

	const int L = s.size();

	int res = 0;
	REP( i, 0, L )
	{
		REP( j, i + 3, L )
		{
			if ( s[ j - 3 ] == 'b' && s[ j - 2 ]  == 'e' && s[ j - 1 ] == 'a' && s[j] == 'r' )
// 			if ( s.substr( j - 3, 4 ) == "bear" )
			{
				res += L - j;
				break;
			}
		}
	}

	cout << res << endl;

	return 0;
}