Come trovare la sottostringa comune più lunga usando gli alberi?

Question

Il problema di sottostringa comune più lungo secondo wiki può essere risolto utilizzando un albero di suffisso.
Da wiki:

Le lunghe stringhe comuni di un insieme di stringhe possono essere trovati da costruzione di un albero suffisso generalizzato per le corde, e poi trovare più profondi nodi interni che hanno nodi foglia da tutte le stringhe nella sottostruttura di sotto di essa

non ottengo questo.
Esempio: se devo:
ABCDE e XABCZ
poi l'albero suffisso è (alcuni rami da XABCZ omessi per motivi di spazio):

La più lunga sottostringa comune è ABC ma non è che posso non vedere come la descrizione di wiki aiuta qui.
ABC non è il nodo interno più profondo con nodi foglia.
Qualche aiuto per capire come funziona?

Answer 1

Non hai effettivamente disegnato l'albero del suffisso. Se lo avessi fatto correttamente, alla radice avresti solo un personaggio possibile una volta. L'albero si divide solo quando una singola lettera può avere più suffissi successivi. Ciò costringe insieme sottostringhe comuni nell'albero, che le rende rintracciabili.

Answer 2

Come quello che è stato detto prima, il tuo albero non è corretto.

Questo è ciò che ottengo eseguendo "ABCDE $ XABCZ" tramite il mio codice.

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 un (compatto) albero suffisso, è necessario trovare il nodo interno più profondo (s) che hanno nodi foglia di tutte le stringhe. Se hai più nodi alla stessa profondità, devi confrontare la lunghezza della stringa rappresentata da quel nodo. cioè ABC, BC e C hanno tutti la stessa profondità, quindi è necessario confrontare la lunghezza delle stringhe ABC, BC e C per vedere quale è più lungo; che è ovviamente 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 un (non compatto) albero dei suffissi, trovare il nodo interno più profondo (s) che hanno nodi foglia di tutte le stringhe.

Spero che aiuti.