明日SA-ISを実装したい
SA-ISは常識っぽいので実装しなければならない。
結構ブログも見つかるので。
明日からはsuffix arrayやろう
suffix treeの線形時間構築アルゴリズムをちらっと見た。これ、suffix arrayの線形時間構築アルゴリズムの元となっているのかな、と思った。
とりあえずsuffix array線形時間構築は必ず実装する。
Manacher's algorithm
my wikiに書いたものを貼り付けてみるテスト。htmlそのまま貼り付けられるけれど、互換性無いから手直ししないとだめだね。
アルゴリズム
「回文の中心」を考えるために、奇回文のみを考える。 偶回文に対応するために、文字列の間になんでもいいダミーの文字を挟む。 例えば、"abcb"を"a#b#c#b"とする。 すると、ダミー文字が中心の回文が偶回文に対応する。
文字列を左から見ていく。 今までで見つけた回文の中で、右端が最も右にあるものを記録しておく。
記録した回文に含まれている部分までは、現在の位置と対称的な位置にあるすでに求めた回文半径だけ一致している。 記録した回文に含まれていない不明な部分は普通に文字列をループで比較して伸ばせる。これを繰り返す。
最初にダミー文字を挟んだが、そのせいで、その文字列で回分半径を求めた結果は元の文字列の回文直径となっている。
なぜ線形時間か
内側のループは記録した右端から始まる。 また、右端以降がマッチしたとしたら今の回文が新たに記録され、右端も更新される。 ここで、記録された右端は一定方向にしか動かない。かつ、内側のループは、最大でも右端が動いた距離+1回しか回らない。 そのため右端でバウンドできる。右端が最大でもΘ(n)であることから、計算量はΘ(n)となる。
range treeとか(segment treeとかにΘ(その区間サイズ)の構造全部乗っけちゃうやつ)
警告:全く実装してないので信頼性低低。結構間違っていそう!そのうち実装してみてその時また書く。
なんかマイナー?。実際自分も覚えてなかった。
d次元ならsegment treeのsegment treeのsegment treeの…っていうふうにすればよい。(実際には~3次元くらいしか使えなさそう。メモリが…あと全探索より遅くなる)
G番目の数字とかこれでもいけそう。log^3ではメモリやばそうだけどWaveletMatrixをsegment treeに乗せればlogを2個にできると思う(確認・実装してないから結構弱い「たぶん」だけど…)。
空間はΘ(n log^d n)となる。まあ当たり前なんだけど、豪快なわりに、という感じで。結構今までその感覚が無くて考えてなかった。空間の定数倍は無い(乗せるデータのサイズだけ)ので結構いけそう。
時間はΘ(log^(d-1) n)が掛け算される。データをマージして処理する必要があるから、乗せるデータ構造によって上手くいかない可能性がある。
segment treeなんだけど今回は静的なクエリ問題重視。動的なものにも適用できるけれど、データ構造がまた動的な変更に対応している必要がある。
ベースはsegment treeだけじゃなくて平衡木にも適用できる可能性がある。でもデータ構造が動的なマージに対応してないと大変なことになる気がするから上手くいかないと思う。
sorted配列
たとえばその区間の値をソートした配列を乗っけちゃう。名前、ありそうだけど不明。
見た目がmerge sortそのままである。実際構築はmerge sortの途中の配列も残しとく感じでΘ(n log n)。
すると区間内のx以下の数の数え上げクエリ、つまり「2次元」クエリがΘ(log^2 n)でできる。やり方:各ノードに対してx以下の数を二分探索で数えて足す。
区間内のk番目の数クエリは単純には二分探索すればΘ(log^3 n)だけれど…。
Fenwick tree / segment tree / 平衡木
区間内k番目の数Θ(log^2 n)?
各segment treeはそのsorted 区間の列を持つ…としたらうまくいかない。マージ上でΘ(log n)でやる場合には、値自体(全体でのインデックスで大きさnに圧縮できる)を分割する感じで揃えなければいけない。値→boolフラグを持って、そのフラグの数をノードが持つやつ。
でも、全部が全部その構造を単なるsegment treeで持ったら、今度はサイズが全体でΘ(n^2)になってしまう!
これは動的にノードを作ることで解決できる。ただし…まだサイズに注意。今度は単純にΘ(n log n)とはいかない…?なぜなら、動的にしてもなおsegment treeのノード数がその区間の幅ではないから。O(n log^2 n)ではあるが…lower boundはどうだろ。少し考えたらわかる気もするけど…?不明。考えるべき。
動的更新
各ノードのデータ構造を動的に更新することもできる、と思う。
ただし、例えば値の書き換えならば値でインデックスされた動的segment treeか平衡木が必要、と思う。
あと、動的な下から上へのupdateが実際にはΘ(n)とかかかって行えないので、更新のたびに適切に処理する必要がありそう。
あと遅延伝播(lazy propagation)は難しそうだができないことはなさそう?
コメント
"?"ばっかりで内容が無いよう。そのうち実装する。
自分が今まで全く考えられていなかったので。一応有名なプログラミングコンテストでのデータ構造の最後にも少し記載あるのだけれど、全然気に留めていなくて。
問題作りとしては、結構マイナー?なので結構できそう?。乗せる構造を工夫したり更新を工夫したら面白くなりそう。
ポイントとして、このデータ構造は「建前上」segment treeとかのパーツの知識だけで実装できるということ。そのおかげで出題しやすいかもしれない。関係ない話として:よくそういう考え方あるけれど、あくまで建前だなあとか個人的には思う。
mywikiは大変
書こうと思っても全然時間がかかって。それくらいしかできなかった。
明日はSuffix TreeにLowest Common Ancestor(Euler Tourでの±RMQへの還元)を適用してApproximate Matchingとかやりたい。
LCAのとかmy wikiとか
LCAのやつ、なんとなくはわかったけれども、文章に説明することはまだできないほどにまとまっていなかった。
自分で理解したことをまとめて実感しようかと、少し前にローカルにmediawikiを立ててみてた。
wiki編集難しい。時間もかかってしまう。個人でやってるらしい http://akademeia.info/index.php?FrontPage とかすごいと思う。
もしある程度記事ができたらpublicにしたいところ。でも公開の仕方わからない?