GO FOR IT(3)暗号検索の高速化

php

GO FOR IT 3問目。暗号検索の高速化

問題

文字列の中に現代の出来事が暗号化されているという、映画や書籍が話題になりました。この暗号は、文字列を特定のスキップ数ごとに改行を入れて折り返すと、関連のある文字列が近い距離に配置されるというものです。
たとえば、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」が出力されるようにしてください。


i)実行速度にこだわらず、読みやすいように書いてください。
ii)アルゴリズムの工夫により、さらに高速化したものを書いてください。

キーワードを入力するとスキップ数と位置を出力するプログラムを作成しろって問題？
これはかなり手ごわそうです。

とりあえず、ランダム文字列を作成するプログラムだけ書いて、続きは明日また取り組もうと思います。
今回はchr関数を使ったのですが、英語の大文字と小文字どちらも作成されますし、'や\などの記号も現れてしまうんですけどいいのでしょうか…。

ランダム文字列を作成するプログラム

<?php

$r = 16;
$rand_str = array();
for($i=0;$i<300000;$i++){
	$r = ( $r * 1103515245 + 12345 ) & 0xFFFFFFFF;
	$rand_str[$i] =chr(0x61 + ( 26 * ( $r / 0x10000) ) / 0x10000);
}
print_r($rand_str)