[Go For It] 暗号検索の高速化

Go For It の3問目。文章に隠された暗号を探すという問題。
例によってプログラムはGithubに上げておいたのでそちらを参照。

https://github.com/shogo82148/GoForIt/tree/master/q03

アルゴリズム自体は簡単で、スキップ数と位置の組み合わせを選んでキーワードと一致しているか試しているだけ。
Pythonでシンプルに書くとこんな感じ。

#!/usr/bin/env python
# -*- coding:utf-8 -*-

import sys

def main():
    word = sys.argv[1]
    rword = word[::-1]
    R = raw_input()

    for skip in xrange(1,len(R)/(len(word)-1)):
        for i in xrange(len(R)-skip*(len(word)-1)):
            t = R[i:i+len(word)*skip:skip]
            if t==word or t==rword:
                print '%s,%s' % (skip, i+1)

if __name__=="__main__":
    main()

ただしこれを実行すると、ランダム文字列の長さをn、キーワードの長さをmとした時、だいたいn^2/2m 回くらいの文字列の比較が必要です。
この問題は n=30万, m=4 なので、約100億回。検索範囲を多少絞ったものの、さすがにこの比較回数だと時間がかかります。実際Pythonでやってみたら150分かかりました。

そこで、スキップ数と位置の組み合わせを全部試すのではなく、可能性のある組み合わせだけ試すことにします。
スキップ数と位置は、キーワード中の任意の2文字の位置がわかっていれば、一意に決まります。
例えば、長さ300文字のランダム文字列の中身を走査して、文字「s」と「o」が次の位置にあることがわかったとします。

s (出現位置: 100, 120)
o (出現位置: 150, 170, 300)

この時、「sony」というキーワードが出現する可能性があるのは、

スキップ数50, 位置100(sが100文字目、oが150文字目)
スキップ数70, 位置100(sが100文字目、oが170文字目)
スキップ数200, 位置120(sが100文字目、oが300文字目)
スキップ数30, 位置120(sが120文字目、oが150文字目)
スキップ数50, 位置120(sが120文字目、oが170文字目)
スキップ数180, 位置120(sが120文字目、oが300文字目)

の6通りのみです。
文字の種類がa〜zまでの26種類あるので、30万文字中、それぞれの文字は大体1万回程度現れると期待できます。
全部の組み合わせを試すと1万×1万＝1億回。1/100になりました。

ここまでは簡単。もうちょっと頑張って工夫して見ました。

先ほどの例の続きを考えましょう。
列挙したスキップ数と位置の組み合わせはあくまで候補なので、元のランダム文字列を参照して答えであるかどうかを確かめます。
はじめの2文字はすでに存在することがわかっているので確かめなければならないのは次の文字です。

スキップ数50, 位置100(200文字目がn?、250文字目がy?)
スキップ数70, 位置100(240文字目がn?、310文字目がy?)
スキップ数200, 位置120(500文字目がn?、700文字目がy?)
スキップ数30, 位置120(180文字目がn?、210文字目がy?)
スキップ数50, 位置120(230文字目がn?、280文字目がy?)
スキップ数180, 位置120(480文字目がn?、560文字目がy?)

実際にランダム文字列を参照してこれを確かめれば良いのですが、元のランダム文字列は300文字しかありません。
301文字以降と比較しようとしている「(スキップ数70, 位置100), (スキップ数200, 位置120), (スキップ数180, 位置120)」は、ランダム文字列を参照するまでもなく、不正解だとわかります。

このような候補を除外するのは簡単ですが、除外するのにも時間はかかります。はじめから候補に含まない方法は無いでしょうか。

そこで、「キーワードのはじめの2文字の位置」ではなく「キーワードの先頭と末尾の位置」から候補を作ればいいのではと考えました。
先頭と末尾が範囲内にあれば、キーワードの途中での範囲外か否かのチェックは不要となります。

しかし、それだけでは候補の数は変わりませんね。もうひと工夫します。
「キーワードのはじめの2文字の位置」を使った場合、スキップ数は2つの文字の距離から簡単にわかりました。
「キーワードの先頭と末尾の位置」を使った場合は単に距離からは直接わからず、次のように計算する必要があります。

　　スキップ数＝(末尾位置−先頭位置)÷(キーワードの長さ-1)

スキップ数は文字数なので整数であるはずです。そのためには、末尾位置と先頭位置は次の関係を満たす必要があります。

　　末尾位置−先頭位置＝(キーワードの長さ-1)の倍数

これは「(キーワードの長さ-1)を法としたときの合同関係」ですね。

この条件を満たすのは「文字の位置 mod (キーワードの長さ-1)」が等しいもの同士なので、これを使ってグループ分けをしておき、グループ内のみで候補を作れば、余計な候補を作らずに済みます。

候補の数は1/グループの数になるので、今回の場合、候補数は1/3、およそ3000万まで減ります。はじめの1/300です。

定数部分は少なくなったけど、O(n^2)なのは変わらず。もっとオーダーが少ない方法があるのかもしれないけど、これで実装。Pythonで作ったら処理時間が結構長くなってしまったので、今回はC++で。Pythonで40秒かかってたのが、C++では4秒になりました。さすがC++。

追記：
C++には最適化オプションがあるのを忘れてました。-O3をつけたら0.6秒で終わりました。さすがC++。