Suffixbäume Flashcards
1
Q
Wie berechnet man Suffix- und LCP-Array aus einem Suffixbaum?
A
Tiefensuche
Suffix-Array = Reihenfolge der Blattknoten
LCP-Array = minDepth bei Blattknoten
an Blatt: minDepth = Blatttiefe
beim Aufsteigen minDepth um Anzahl aufgestiegene Zeichen erniedrigen
2
Q
Wie berechnet man einen Suffixbaum aus Suffix- und LCP-Array?
A
Einfügen der Suffixe aus Suffix-Array in Reihenfolge
je dazwischen: Aufstieg um Stringtiefe - LCP[i] Zeichen
Stringtiefe = |s| + 1 - SA[i]
