夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

最長共通部分文字列についての考察

プログラミング

久しぶりにアルゴリズム考察します←というか前例ほぼ０
まぁ最長共通部分文字列と最長共通部分列という非常に紛らわしい二問があるために色々とドジを踏んでしまうので、もうそれなら両方の解法をしっておこうというわけです(´・ω・｀)
後者はDPなのでその時その時頑張るとして、前者は考え方が難しいです。はい。
というわけで調べてみました。

1.データ構造を使わずに（？）やる方法

とりあえず最長共通部分文字列でぐぐるともっともはっきり解法が書かれているのはqnighyさんのブログですが、ここではおそらくデータ構造を使っていない方法が載ってます。
オーダーはO（（n+m）min（n,m））ぐらいで、要旨だけ説明するとS1,S2とあったときS1のある文字とS2のある文字から始まる最長の部分文字列を総当たりするのを多少の工夫でオーダーを落としてるような感じです。
コードの重要な部分だけ抜き出しておくとこのようなコードになってました。
（長さだけ求めるコードにしてますが、書き加えてその文字列も同時に求めるようにするのは簡単だと思うので省略します。)

int res=0;
for (int off=-(int)s1.size(); off<=(int)s2.size(); off++) {
    int len=0;
    for (int i=max(off,0); i<min(s1.size()+off,s2.size()); i++) {
        if (s1[i-off=!=s2[i]) {
            len++;
            res=max(res,len);
        } else len=0;
    }
}

でもこれはこのオーダーを落とすアイデアを思いつくからこそ出来ることであって、直感的には何をしているのか分かりにくいですし、たぶん普通に同じアルゴリズムを実装したら僕のような頭の悪い人間はO(n^2m^2)ぐらいになってしまうと思います（多分。これを単純に実装したときを試してないので確信もって言えません。すいませんorz）

2. Suffix Tree


さて、ぐぐった時に話を戻すと、これ以外は学術論文やら最長共通部分列のページが並ぶわけですが、その中に接尾辞木、つまりSuffix TreeのWikiが出てきます。
そしてその中には最長共通部分文字列がΘ(ni + nj)で求められると書いてあるんですね(　＾∀＾)
まぁΘという記号はここを見といてください。あんまり説明できるほど詳しくないので。
それはともかく、このデータ構造を知ってさえいれば、他の問題を解くときにも使えますし、早い。
というわけでこのデータ構造を今回は学んでみたわけです。
とりあえずここでは概略のみを。。。
接尾辞木とは名前の通り文字列の接尾辞を木構造で管理するものです。
イメージとしては画像のような木なのですが・・・これもこれでわかりにくいですね(-_-;)Wikiの転載ですが・・・
とにかく接尾辞の集合の基数木です。親は接尾辞の頭文字とかひとつ前の文字とかになって、改行が入ったところが区切りです。つまり改行から上へたどっていくと接尾辞が一つわかるといった感じです←どんな感じだw

3. Suffix Treeを実装してみる・・・苦戦

まぁ理解していないというかぼんやりとした理解しかしてないので苦戦するのも当然かもしれませんが、それだけでなくぐぐってみるとわかるのですが、実装例がPythonぐらいしかありません。
Python実装だとデータ構造だけで軽く150行いきますし（コメント有り）、classやyieldなどを使っていて、チュートリアルの域から脱していない僕には翻訳能力なんてありません(´；ω；｀)まぁそれでもページの解説をよむぐらいの能力はあるのでかいつまんでお話します。
まず構築にはUkkonen のアルゴリズムと呼ばれる1995年に生み出されたアルゴリズムを使います。
とりあえず、考えられる最も単純な構築方法は接頭辞を長い順にツリーに挿入していく、しかしこれだと時間がかかる・・・ということ、そして文字列をいちいち木にしているとメモリの消費が異常なことになるので区間で管理することにするということを踏まえておいてください。今回の第一目標は最長共通部分文字列を求めることなので接頭辞木の基礎の基礎はどんどん割愛していきます。
さて本題のUkkonenのアルゴリズムに入りますが、これはおおざっぱにいうと文字を読み込みながら構築するという方法です。
そもそも画像で見たようにこの接頭辞木自体根に近づくほど頭文字の方をとっているのでこれがうまくいくことは自明でしょう。
文字列から三文字くらいおきに文字をとってきて、探索し、一致するところがあればそこに入れてしまい、無ければ単純につなげていく・・・というのが方法の概略で参考ページのまとめを引用するとこう書かれています。

接尾辞木をたどって一致した区間が (s, e) とします。このとき、(0, e), (1, e), ..., (s - 1, e) までの接尾辞は接尾辞木に挿入されている、つまり区間 (0, s - 1) の接尾辞木は完成しています。
あとは区間 (s, e) の接尾辞 (s, e), (s + 1, e), ..., (e - 1, e) を挿入すればいいわけです。

しかしこれではどう考えても探索に時間が掛かっていることがわかります。というわけでサフィックスリンクというものを節に持たせることでこの問題を解決しています。
これはまたもやそのまま引用してしまうと節 p から一つ短い接尾辞を持つ節 q へのリンクのことです。画像には点線矢印で書いてあります。便宜的に点線矢印の初めをB、その次をC、その次をAと考えておいてください。まぁ接頭辞で考えたほうがわかりやすいと書かれているので接尾辞での考え方は省略しますが、接頭辞で考えるとまず節Bまでたどって得られる接頭辞はANAとなり、これより一つ短い接頭辞は節CまでたどったNAなのでBからCへリンクを貼ります。どうようにCからA、Aから根とリンクを貼っていきます。

・・・
・・・・・・
これは終わらないんじゃないか？(-_-;)
すこし、光が見えないので一旦ここで終了します。
もっとも重要なことをいっていないのでそれだけいいますと、最長共通部分文字列を解くには一般化接尾辞木を用います。これはS1の接尾辞木にS2を加えたものです。詳しくは参考にしていたこちらをよろしくお願いします。
本当は接尾辞配列にも触れて、比較すると実装が楽なこちらでもやはり最長共通部分文字列を解くことができるのかなどの考察（もしかしたら読むだけかも）をしようと思ったのですが、家帰ってアルゴリズムリファレンスでも見てあったらまた書きます。
とりあえずはここまで(´ε｀；)
中途半端ですいませんでしたorz