Codeforces #188 Div2 B "Strings of Power"
問題
http://codeforces.com/contest/318/problem/B
訳
ボロディアはヘビメタを聴くことと、(たまに)読書をすることが好きである。そのため、ボロディアは好きな音楽ジャンルについての文章が特に好きであった。
ボロディアは"heavy"で始まり"metal"で終わる文字列をパワフルだと呼んでいた。最近、彼はこのような文章を読んでいると膨大なエネルギーを感じる。だからボロディアは好きなアーティストが書いた文章からパワフルな部分文字列の数を数え、そして、一日中それを自慢しようと決めた。彼を助けるため、与えられる文字列のに含まれる、パワフルな部分文字列の数を出力せよ。
制約
1 <= 文字列の長さ <= 10^6
考えた事
サフィックスが出てきたら、そこまでに出てきたプレフィックスの総和分、パワフルな部分文字列が増える。
プレフィックスとサフィックスの検知が一番やっかいだった・・・
ソースコード
int pre[1000050]; int suf[1000050]; int main() { string str; int n; cin >> str; n = str.length(); // プレフィックスのインデックスを取得 memset( pre, 0, sizeof(pre) ); string target = "heavy"; int p = 0; for( int i = 0; i < n; i++ ){ if( str[i] == target[p] ){ p++; if( p == 5 ){ pre[i-4] = 1; p = 0; } }else if( str[i] == target[0] ){ p = 1; }else{ p = 0; } } // サフィックスのインデックスを取得 memset( suf, 0, sizeof(suf) ); target = "metal"; p = 0; for( int i = 0; i < n; i++ ){ if( str[i] == target[p] ){ p++; if( p == 5 ){ suf[i-4] = 1; p = 0; } }else if( str[i] == target[0] ){ p = 1; }else{ p = 0; } } // プレフィックスの総和を出しておく for( int i = 1; i < n; i++ ){ pre[i] += pre[i-1]; } // サフィックスがでてきたら、 // プレフィックスの総和を答えに足す long long ans = 0; for( int i = 0; i < n; i++ ){ ans += suf[i] * pre[i]; } cout << ans << endl; }