概要
文字列 s が与えられる。 が文字列 "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; }