DNA synthesizer(DNAの合成) - joi2010-day2 解説

筆者: qnighy

与えられた素文字列群を、1文字以上の「のりしろ」を残しつつ繋げ、最小個数で目的の文字列を構成する方法を答えさせる問題である。

(構成したい文字列の長さ=L, 素DNA鎖の長さの最大値=Sとおくことにする)

O(SNL)解法

一見すると動的計画法のようであるので、漸化式を立てよう。

最初からi文字目までの文字列をちょうど構成できる場合の最小個数をdp[i]とおくと

dp[i] = min{最後のa文字が素DNA鎖に存在するとき、dp[i-a],dp[i-a+1],…}+1

それぞれの位置で長さSの文字列をN回マッチングすればいいので、O(SNL)で計算可能。

この方法で30点を獲得できる。

これをO(SL)にするためには、Trieを使用すればよい。

Trieとは、複数の文字列からプレフィックス検索するための簡単な木である。

文字が辺に対応し、例えば「ACCT」と検索するときは、根からA,C,C,Tの順に辺をたどる。

Trieを逆向きに構築すれば、前述のO(SNL)解法におけるNを削減することができる。Trieの構築にはO(SN)かかるので、合計O(SN+SL)で終わる。これなら満点が期待できる。

Aho Corasick法を用いることで、さらに短い時間で解くことができる。

Aho Corasick法はKMP(Knuth-Morris-Pratt)法と同様の手法をTrie木に適用したもので、マッチに失敗したときにその結果を破棄するのではなく適切な遷移を行うことで効率よくインクリメンタルに検索できるようにする仕組みである。

その基本的な考えは、例えば次のとおりである：現在「…CCTA…」とマッチしていたとして、次の文字がGのとき、「…CCTA[G]…」だとマッチしないが、「…TAG…」ならマッチする。このような状態遷移をfailure linkと呼ぶ。これはTrie木を幅優先探索しながら構築することができる。

Aho Corasick法をこの問題に適用すると、目的の文字列を順番に走査していくとき、各時点でその位置の直前に作れる文字列の最大の長さが線形時間で得られる。これとスタックを組み合わせると、O(L)時間で走査ができる。

Aho Corasick法のためのオートマトンの構築はO(SN)時間でできるので、結果としてO(SN+L)時間で計算できる。