読者です 読者をやめる 読者になる 読者になる

あったこといろいろ

ほぼ自分用備忘録です。

ICPCアジア地区つくば大会D問題 「Hidden Anagrams」

※これは参加記ではありません。参加記は別記事で上げます。

問題: AIZU ONLINE JUDGE

問題概要

長さ 4000 以下の S1 と S2 が与えられる。
文字列Sの部分文字列を S' と呼ぶことにする。
「S1' が S2' のアナグラムとなるもの」のうち最長のものの長さを求める。

入力
anagram
grandmother

出力
4

解法

S1とS2のうち短い方の長さをNと呼ぶことにする。
一致判定をする部分文字列の長さLを 1~Nまで変化させながら、各Lにおいて以下の処理を行う。

  • 文字列のアナグラムの一致判定は、文字列を構成する文字のヒストグラムの一致判定と等しいので、部分文字列を長さ26のarrayで表現する。
  • 長さLとなる部分文字列のヒストグラムを記録するmapを用意する。
  • 長さLの、S1の部分文字列ヒストグラムをしゃくとり法の要領で列挙し、mapに記録しておく。
  • この判定によりアナグラムが一致するものが見つかれば、最長の長さの値を更新していく。


空間計算量がO(文字列長)になるので余裕を持って通ります。
mapを使いまわさず、「長さLのヒストグラムは map[L] に格納する」という実装をするとMLEしてしまいました。
つくば会場ではMLが非常に大きかったようなので、本番ではmapを使いまわさなくても通っていたように思います。


gist.github.com