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に記録しておく。

• 長さLの、S2の部分文字列ヒストグラムをしゃくとり法の要領で列挙し、同じヒストグラムがmapに記録されているか(=S1に同様の部分文字列ヒストグラムがあるか)を調べる。

• この判定によりアナグラムが一致するものが見つかれば、最長の長さの値を更新していく。

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

gist.github.com