Wie finde ich den längsten gemeinsamen Teilstring mit Bäumen?

Question

Das längste gemeine Teilstring-Problem nach Wiki kann mit einem Suffix-Baum gelöst werden.
Von wiki:

Die längste gemeinsame Teil eines Satzes von Zeichenketten kann durch Aufbau einer verallgemeinerten Suffix-Baum für die Saiten, und dann finden die tiefsten inneren Knoten gefunden werden, die Blattknoten von allen Saiten im Unterbaum darunter

Ich verstehe das nicht.
Beispiel: wenn ich:
ABCDE und XABCZ
dann wird der Suffix-Baum ist (einige Zweige von XABCZ Platzgründen weggelassen):

Die längsten gemeinsamen Teilzeichen ABC sind, aber es ist nicht kann ich nicht sehen, wie die Beschreibung von Wiki hier hilft.
ABC ist nicht die tiefsten internen Knoten mit Blattknoten.
Irgendwelche Hilfe, um zu verstehen, wie das funktioniert?

Answer 1

Sie haben den Suffixbaum nicht gezeichnet. Hättest du es richtig gemacht, hättest du an der Wurzel nur einmal jedes mögliche Zeichen. Der Baum teilt sich nur auf, wenn ein einzelner Buchstabe mehrere folgende Suffixe haben kann. Das zwingt gemeinsame Teilstränge im Baum zusammen, was sie auffindbar macht.

Answer 2

Wie bereits erwähnt, ist Ihr Baum falsch.

Dies ist, was ich bekomme, wenn "ABCDE $ XABCZ" über meinen Code ausgeführt wird.

Suffix Tree code:

String = ABCDE$XABCZ$ 
End of word character 1 = $ 
└── (0) 
    ├── (20) $ 
    ├── (22) ABC 
    │ ├── (15) DE$ 
    │ └── (23) Z$ 
    ├── (24) BC 
    │ ├── (16) DE$ 
    │ └── (25) Z$ 
    ├── (26) C 
    │ ├── (17) DE$ 
    │ └── (27) Z$ 
    ├── (18) DE$ 
    ├── (19) E$ 
    ├── (21) XABCZ$ 
    └── (28) Z$ 

In einem (kompakt) Suffixbaum, müssen Sie den tiefsten inneren Knoten (n), die Blatt finden Knoten von allen Saiten haben. Wenn Sie mehrere Knoten in derselben Tiefe haben, müssen Sie die Länge der von diesem Knoten dargestellten Zeichenfolge vergleichen. d. h., ABC, BC und C haben alle die gleiche Tiefe, daher müssen Sie die Länge von ABC-, BC- und C-Strings vergleichen, um zu sehen, welche länger ist. Das ist natürlich ABC.

Suffix Trie code:

└── null 
    ├── A 
    │ └── B 
    │  └── C 
    │   ├── D 
    │   │ └── (E) ABCDE 
    │   └── (Z) ABCZ 
    ├── B 
    │ └── C 
    │  ├── D 
    │  │ └── (E) BCDE 
    │  └── (Z) BCZ 
    ├── C 
    │ ├── D 
    │ │ └── (E) CDE 
    │ └── (Z) CZ 
    ├── D 
    │ └── (E) DE 
    ├── (E) E 
    ├── X 
    │ └── A 
    │  └── B 
    │   └── C 
    │    └── (Z) XABCZ 
    └── (Z) Z 

In einer (nicht kompakt) Suffixbaum, finden Sie die tiefsten inneren Knoten (n), die Blattknoten von allen Saiten haben.

Ich hoffe, es hilft.