Suffix arrayでのbottom-up traversalがうまくいかない

"Replacing suffix trees with

enhanced suffix arrays"に書かれているのを書きたいのだけれどうまくいかない。Lempel Ziv decompositionの場合子のリストを持ってさらにそれに値も持たせないといけないっぽいのだけれど、一時領域だけで最悪24n bytesとかかかってしまう。

まずノードが(l,r)の組で表わされるのが扱いづらい。それをインデックスとした配列を直接操作できない。子を列挙できてもそれに対応する値を保存・取得する方法がわからない。そのためスタックに載せないといけなくて、そのため子のリストを陽に持たないといけなくなってしまう。

あとchild-tableとかlcp-arrayとかが現実的には小さい値ばかりだからたいていは2n bytesとかで～みたいなことをいってるのだけどどうしても最悪を考えてしまう。

lcp-arrayに関しては別に簡潔な保存の方法もあるらしいのだが…読めてない。

なにかうまい方法があるのか…ジェネリックなtraversalルーチンはただの理論的な興味深さでしかなく、問題には問題ごとに対応しなければならないのか…