Suffix Treeで遊んでた

構築の時はともかくDFSするとなるとスタックオーバーフローするよなーとか思った。木の深さは(replicate n 'a')でnを達成する。なんでも、メモリを定数倍でも削減しようと思うと、結構複雑になる気がする。現実的にはそれが必要な場面も多いだろうし。

Suffix TreeはSuffix Array(+LCP)に負けてるってつくづく思える。でも木は見やすいし、考えやすいと思う。

あと、ふとマルチバイト文字セットに対してはどうできるかな、と考えてみた。まず思いついたのが、まず8bitで処理してその後「中途半端な位置にある」ノードを識別するテーブルを作って、検索の時にはそれを元にはじく、というもの。現実的にはマルチバイトでやることが多いだろうし、何らかのアルゴリズムが実装されてるのかなー。

基本的だけど、現実的であってそれなりに面白い問題だと思う。