2/8追記：ライセンスについて
※回答はオープンソースソフトウェアとして公開してください。
その際、そのソフトウェアをOSDに準拠したライセンス(GPLライセンスやBSDライセンスなど)であることを明示して公開してください。
とあるので、ここのコードは修正BSDライセンスとして扱って下さい。普段は常識的な範囲でご自由にライセンスにしておくのだけど、OSSの世界ではそれは困るらしい。
ソニーのソフトウェアスペシャリスト認定コンテスト『暗号検索の高速化』
前回、前々回に続いて『暗号検索の高速化』をやってみました。。。が、どうも問題を読み間違えたらしい。
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文字以上のキーワードがランダム文字列中のどこにあるかを最小スキップ順に高速に求めたいと思っています。
例題の再現
とりあえず、このランダム文字列を作ってみることにします。これは簡単で
#include < stdio.h>
int main()
{
unsigned long long r = 16;
int i = 0;
char rand_str[300000];
for( i = 0; i < 300000; i++ )
{
r = ( r * 1103515245 + 12345 ) & 0xFFFFFFFF;
rand_str[i] = 0x61 + ( 26 * ( r / 0x10000) ) / 0x10000;
}
rand_str[i] = ' ';
i = 0;
while(rand_str[i] != ' ')
{
for( int j = 0; j < 4162 && rand_str[i] != ' '; j++ )
putchar(rand_str[i++]);
puts("");
}
return 0;
}
というコード実行すればOK。ところが得られたものでソニー側の出題と照らし合わせると
といった感じで逆になっているような・・・？たとえばsonyのsの前後がサンプルではvdsidだけど、自分のはdisdvと逆順になっている。仕方がないので逆順に出力するようにして
// Paste me into the FileEdit configuration dialog
#include < stdio.h>
#include < stack>
using namespace std;
int main()
{
unsigned long long r = 16;
int i = 0;
stack< char> rand_str;
bool exitflag = false;
while( exitflag == false )
{
for( int j = 0; j < 4162; j++ )
{
r = ( r * 1103515245 + 12345 ) & 0xFFFFFFFF;
rand_str.push( 0x61 + ( 26 * ( r / 0x10000) ) / 0x10000 );
i++;
if( i == 300000 )
{
exitflag = true;
break;
}
}
while( !rand_str.empty() )
{
char c = rand_str.top();
rand_str.pop();
putchar(c);
}
puts("");
}
return 0;
}
これで出力が逆順になり、
サンプル通りになる。でもオフセットアドレスが211,684になっている。改行文字があるけどここまで大幅にずれはしないはず。気を取り直して次に行きます。
暗号検索その1
文字列を検索するときはしっぽから探すのが効率がよい。例えば「あいうえお」という文字を探すとして、いま注目しているのが「あいうえこ」だとする。そうすると4文字目まではあっているのに5文字目が違うので無駄になる。最初から「お」を探して4文字目が「え」、3文字目が「う」・・・と逆順に辿れば無駄が少ない。
で、matrixを縦横にサーチ（たぶんこれ勘違い）していけばよいので、その通りにコードを書きます。たぶん勘違いなので清書する気がしないから汚いけどのそのまま載せます。
#include < stdio.h>
#include < string>
#include < set>
#include < map>
#include < algorithm>
#include < stack>
using namespace std;
// characters per line
const int cpl = 4162;
int matrix[] = {1, -1, cpl, -cpl};
int main( int c, char *v[] )
{
if( c != 2 )
{
fprintf( stderr, "%s keywordn",v[0] );
return EXIT_FAILURE;
}
string keyword = v[1];
string reverse = keyword;
std::reverse( reverse.begin(), reverse.end() );
set< char> k;
for( int i = 0; i < keyword.length(); i++ )
k.insert(keyword[i]);
map< int, char> m;
int loc = 0;
while(!feof(stdin))
{
char ch = fgetc(stdin);
if( k.count(ch) != 0 )
m.insert(make_pair< int, char>( loc, ch ));
loc++;
}
struct node
{
int address;
int depth;
int direction;
};
stack< node> s;
for( map< int, char>::iterator it = m.begin(); it != m.end(); it++ )
{
node n;
if( it-> second == reverse[0] )
{
n.address = it->first;
n.depth = 1;
s.push(n);
}
}
while( !s.empty() )
{
node n;
n = s.top();
s.pop();
// 脱出条件をここに書く
if( reverse.length() == n.depth )
{
map< int, char>::iterator it = m.find( n.address );
if( m.end() != it )
{
fprintf( stdout, "%d, %dn", matrix[n.direction], n.address );
}
continue;
}
// ここでノードの枝を全部辿るループを書く
if( n.depth == 1 )
{
// 4方向ループ
for( int i = 0; i < 4; i++ )
{
map< int, char>::iterator it = m.find( n.address + matrix[i] );
if( m.end() != it && it->second == reverse[n.depth] )
{
node next;
next.address = n.address + matrix[i];
next.depth = n.depth + 1;
next.direction = i;
s.push(next);
}
}
}
else
{
// 一方向のみ
map< int, char>::iterator it = m.find( n.address + matrix[n.direction] );
if( m.end() != it && it->second == reverse[n.depth] )
{
node next;
next.address = n.address + matrix[n.direction];
next.depth = n.depth + 1;
next.direction = n.direction;
s.push(next);
}
}
}
return 0;
}
何をしているかだけ解説。まず引数を見てキーワードを取得します。ついで、そのキーワードを反転させます。
次にsetを用意します。これは重複を許さない集合ですが、つまり例えばsonyなら”s”, “o”, “n”, “y”が入っていて欲しいのです。neetなら”n”, “e”, “t”になります。
map
で、1文字ずつがしがし標準入力から読み込んで、何文字目がなんであるかをmapにげしげし放り込んでいきます。その際にキーワードと全く関係ないのが入っていると効率が悪いので、さきほどのsetに問い合わせて該当する文字だけmapに追加します。setに「sは何個ありますか？」と問い合わせると、重複を許さない集合なので0か1を返します。0でなければキーワードに含まれる文字であるとわかります。
ここまできたら、あとは力業で深さ優先探索というのをやります。
図はWikipediaから拝借。この赤い丸を仮にノードと呼びます。これを次々に渡り歩いて目的のものを探します。今回必要なのは、まず文字の位置、深さ（sonyなら4文字まで探索して合格ならおしまい）、最後にスキャンしている方向（たぶん勘違い）です。
次に初期ノードを登録します。sonyだったら”y”で始まっているところが初期ノードですから、がしがし突っ込みます。最初だけは縦横どっちにスキャンするか不明なので4方向スキャン、2回目からは決めた方向に突き進むスキャンをします。コードコピペだけどうまくまとめるべき。でも面倒だからやらない。
初期ノードが決まったらあとはループを回して脱出条件を決めて、脱出条件に該当しなければたどれるノードを全部たどっていきます。大まかな説明はこんな感じ。この手の探索のコードは
が網羅的かつ詳細に載っているのでお勧め。
さて、これを
cat sample.txt | ./a.out sony > a.txt
のように食わせると
-4162, 255154 -4162, 226422 4162, 224120 -4162, 144222 1, 118593
のような結果を返します。一番小さいのは一番下だからこれが答え・・・だと思ったけど多分違う。
勘違い
たぶんこの問題は
この文字列を4162文字ごとに改行を入れて折り返し、”sony”の文字列が中央付近に配置されるように、19桁10行の範囲を抜き出すと、下記のようなマトリクスが得られます。
と折り返すというのは見やすくするためのものであって、4162文字ごとに改行を入れて縦横にスキャンしろという問題ではないっぽい。つまり3文字おきに読んでsonyになるとかそういうのでもよく、
- スキップ数が短い順に出力してください。
- スキップ数が同じ場合は、ランダム文字列先頭に近いものから出力してください。
- キーワード文字列が逆順にマッチした場合も出力してください。
3文字おきに読んでOKならそっちのほうがいいわけです。先ほどのサンプルだと1文字おき（横に並んでいる）のもあります。キーワードが逆順にマッチした場合というのも（横書きで）左に何文字かスキップしていって読めればOKということでしょう。
というわけで、このプログラムは題意を満たさないのでまた作り直しです。たぶんつづく。
最近のコメント