1)問題文
文字列の中に現代の出来事が暗号化されているという、映画や書籍が話題になりました。この暗号は、文字列を特定のスキップ数ごとに改行を入れて折り返すと、関連のある文字列が近い距離に配置されるというものです。
たとえば、r=16、i=0を初期値として、下記を300000回繰り返して生成した、’a’から’z‘までの文字をランダムに含むアスキー文字列rand_str[]には、先頭208728文字目から4162文字スキップで"sony"の文字列が存在します。
r ← ( r * 1103515245 + 12345 ) & 0xFFFFFFFF
rand_str[i] ← 0x61 + ( 26 * ( r / 0x10000) ) / 0x10000
i ← i + 1
この文字列を4162文字ごとに改行を入れて折り返し、"sony"の文字列が中央付近に配置されるように、19桁10行の範囲を抜き出すと、下記のようなマトリクスが得られます。
--省略--
このマトリクスには、"alpha"の文字列が等距離スキップで存在し"sony"の文字列と近い距離にあります。この暗号では最小スキップの文字列が重要な意味をもち、2文字以上のキーワードがランダム文字列中のどこにあるかを最小スキップ順に高速に求めたいと思っています。
なお、高速実行可能であれば使用プログラミング言語や入出力仕様は問いません。たとえば、キーワードをコマンドラインで指定し、ランダム文字列を標準入力から得て、スキップ数と位置をカンマで区切ったものを改行し、標準出力するようなプログラムを作成してください。
・ スキップ数が短い順に出力してください。
・ スキップ数が同じ場合は、ランダム文字列先頭に近いものから出力してください。
・ キーワード文字列が逆順にマッチした場合も出力してください。
※ たとえば前述のランダム文字列から、"sony"の逆順の"ynos"を探す場合には、「4162,208728」が出力されるようにしてください。
2)解き方
例えばSONYであれば、Sを見つけその位置を記録、次にOを見つける、そして２つの差分×2と3でNとYに辿りつけたら、それは等距離スキップということになる。
それをC++を用いて記した。
また、２つ目の解き方として、SONYならば、(S+Y)%3 = 0であるとき、(S+Y)/3 = 距離スキップ。これを用いて、S、S+等距離スキップ、S+等距離スキップ*2・・・・とやれば上記より早く出来るのではないかと考えた。結果として一つ目の方が早かったんだけどね。
3)ライセンス
BSDライセンス
4)ソースファイル
１つ目・・・)main(ソース) 検索部分クラス(ヘッダ、ソース) ランダム文字列作成クラス(ヘッダ、ソース)
２つ目・・・)main(ソース) 検索部分クラス(ヘッダ、ソース) ランダム文字列作成クラス(ヘッダ、ソース)