Suffix-Suffix-Array von Suffix Tree.Inordieren Sie, wenn der Knoten mehr als zwei Kinder hat

Question

aus den Anmerkungen:

Es ist nicht schwer zu beobachten, dass das Suffix-Array $ \ texttt {SA} $ von Der Text $ \ texttt {t} $ kann von seinem Suffix-Baum erhalten werden $ \ texttt {st} $ Indem Sie einen Besuch in der Reihenfolge durchführen: Jedes Mal, wenn ein Blatt ist aufgetreten ist der in diesem Blatt gespeicherte Suffix-Index in die Suffix-Array $ \ TextTt {SA} $ ; Jedes Mal, wenn ein interner Knoten U ist Es ist der zugehörige Wert in das Array geschrieben $ \ texttt {lcp} $ .

Wie machen Sie den Inorder-Besuch, wenn ein Knoten mehr als zwei Kinder hat?

Nehmen wir an, Sie besuchen das linke Kind, dann den Knoten, dann das andere linke Kind. Dann besuchen Sie wieder den Knoten?

sa in einem Array von Zeiger auf Suffixe, bestellt lexikologisch.

lcp enthält das längste gemeinsame Präfix zwischen zwei aufeinanderfolgenden Suffixen $ \ Text {Suff} _ {SA [i]} \ text {und} \ Text {Suff} _ {SA [i + 1]} $ .

Die \ $ repräsentiert ein Zeichen, das kleiner ist als jedes andere char.

Der mit jedem Knoten zugeordnete Wert ist die Länge des bisherigen Präfixs.

Die Blätter repräsentieren die Indizes von Suffixen. Wenn T= Banane \ $, ist das Blatt 3 Nana \ $ (t [3,7])

Im Bild ist das, was ein Suffix-Baum sein soll, aber ich denke, es gibt einen Fehler, da die Kanten nach ihrem Etikett sortiert werden sollen, und das Blatt 7 mit der mit der Markierung "\ $" sollte das linke Blatt sein Rand.

Wenn Sie den Algorithmus simulieren, besuchen Sie zuerst den Knoten 7 (unter Verwendung der festen Version des Baums), dann die Root, so dass Sie

haben generasacodicetagpre.

Nehmen wir dann an, Sie machen weiter mit einem Inorder-Besuch von u. Wenn Sie zum Root zurückkehren, geben Sie den Wert 0 erneut in den LCP ein? Oder mach es das erste Mal, wenn du die Wurzel besucht hast?

Answer 1

Wenn ein Knoten $ L $ Kinder verfügt, mit $ l \ geq 2 $ während des InordersBesuchen Sie, dass Sie den ersten $ L-1 $ Kinder als linke Knoten behandeln, und Sie müssen den übergeordneten Multiple ( besuchen)$ l-1 $ ) mal, das Schreiben mehrmals die Länge des Präfixs im LCP-Array schreibt.

Dieses, auf den Baum im Bild angewendet, würde das Richtige ergeben:

generasacodicetagpre.

Beachten Sie, dass der Rand, der "$" mit dem Blatt 7 markiert ist, der linke sein sollte.