Wie finde ich die längste gemeinsame Teilzeichenfolge mithilfe von Bäumen?
Das laut Wiki am längsten verbreitete Teilstring-Problem kann mit einem Suffix-Baum gelöst werden.
Vonwiki:
Die längsten gemeinsamen Teilzeichenfolgen eines Satzes von Zeichenfolgen können gefunden werden, indem ein verallgemeinerter Suffixbaum für die Zeichenfolgen erstellt und dann die tiefsten internen Knoten ermittelt werden, die Blattknoten von allen Zeichenfolgen in der Unterstruktur darunter haben
Ich verstehe das nicht.
Beispiel: wenn ich habe:ABCDE
undXABCZ
dann ist der Suffixbaum (einige Äste ausXABCZ
aus Platzgründen weggelassen):
Die längste gemeinsame Teilzeichenfolge istABC
aber es ist nicht ich kann nicht sehen wie die beschreibung von wiki hier hilft.ABC
ist nicht der tiefste interne Knoten mit Blattknoten.
Irgendeine Hilfe, um zu verstehen, wie das funktioniert?