http://abc032.contest.atcoder.jp/tasks/abc032_b
概要
- sからk文字取り出して、その部分文字列を連想配列に突っ込んで、重複しない数を答える。
高速解法
- ローリングハッシュを生成する。ローリングハッシュには、
hash[a:c] = (hash[a:b]*B**(c-b) + hash[b:c]) % Pという性質がある。 - 今回はhash[i:i+k]が得られれば良いので、この式を
hash[b:c] = ...と変形すれば良い。 - 部分ハッシュを得るのは、
B**(c-b)を事前に計算しておくことでO(1)とできる。 - また、連想配列がハッシュテーブルならば重複判定もO(1)なので、トータルでO(s)となる。
- http://abc032.contest.atcoder.jp/submissions/608838
- ※C++98互換のためunordered_setではなくsetを使っているためこの実装はO(slogs)
まとめ
- 今回の制約では全くの無駄ですので、解法は賢く選びましょう。
- なぜyukicoder復習コンテストのストックにしなかったし。提出後に気づいたので後の祭り。