接尾辞ツリーからの接尾辞配列の構築ノードが2人以上の子供を持っているときの毎日の訪問

Question

ノートから：

接尾辞配列 $ \ texttt {sa} $ を守ることは難しくありません。 テキスト $ \ textttt {t} $ はそのサフィックスツリーから取得できます $ \ texttt {st} $ 挿入訪問を実行することで：葉があるたびに この葉に格納されているサフィックスインデックスが見つかりました。 サフィックス配列 $ \ texttt {sa} $ ;内部ノードUの毎に 遭遇すると、その関連の値は配列に書き込まれます $ \ texttt {lcp} $ 。

ノードに2人以上の子供がいる場合は、InOrder訪問をしますか？

あなたが一番左の子供、そしてそのノード、そして他の最悪の子供を訪問するとしましょう。それからあなたはもう一度ノードを訪問しますか？

SA 接尾辞対位の配列で、辞書学的に並べられた

lcp は、2つの連続した接尾辞の間に最も長い共通の接頭辞を含みます $ \ text {sup} _ {sa [i]} \ text {および} \テキスト{sup} _ {SA [i + 1]} $ 。

\ $は他のすべての文字よりも小さいCHARを表します。

各ノードに関連付けられている値は、これまでにスペルのプレフィックスの長さです。

葉は接尾辞の指標を表します。 T= Banana \ $の場合、リーフ3はNANA \ $（t [3,7]）

を表す

接尾辞の木であると想定されているものがありますが、エッジをラベルに従ってソートする必要があるのでエラーがあると思います。エッジが「\ $」と表示されているエッジで左端の葉であるべきであると思います。エッジ

アルゴリズムをシミュレートするときは、まずノード7（ツリーの固定バージョンを使用して）、次にルートを訪問するので、

SA = [7, ...]
lcp = [0, ...]

.

それでは、あなたがuのInOrder訪問で続けているとしましょう。 rootに戻ると、LCP でもう一度値0を挿入しますか？それとも、あなたが根を訪れたのは初めてそれをしますか？

Answer 1

ノードに $ l $ の子が $ l \ geq 2 $ を持つ場合あなたは最初の $ L-1 $ を左ノードとして扱う必要があり、親の倍数を訪問する必要があります（$ L-1 $ ）回、LCPアレイ内にスペルのプレフィックスの長さを複数回書き込みます。

これは、画像内の木に適用され、正しい：

SA = [7, 6, 4, 2, 1, 5, 3]
lcp = [0, 1, 3, 0, 0, 2]

.

リーフ7と「$」と表示されたエッジが一番左側にあるはずです。