Generierung von Suffixen aus einem Suffix-Baum

Question

Ich habe eine Suffix-Struktur in Java auf der Website hier http://marknelson.us/1996/08/01/suffix-trees/ gebaut, aber ich habe ein Problem festgestellt. Ich kann einen Suffixbaum erstellen, aber ich kann versuchen, einen Satz aller Suffixe aus dem Baum zu erstellen. Ich finde grundsätzlich alle "Endknoten und zurück die Zeichenfolge, die von diesem‚Endknoten‘dargestellt wird

Das Algorithmus für ein Wort wie„Buchhalterin“arbeitet

├── (1) bookkeeper 
├── (9) e 
│ ├── (8) eper 
│ ├── (10) per 
│ └── (12) r 
├── (6) k 
│ ├── (7) eeper 
│ └── (5) keeper 
├── (3) o 
│ ├── (4) kkeeper 
│ └── (2) okkeeper 
├── (11) per 
└── (13) r 

Suffixe:

[bookkeeper, ookkeeper, okkeeper, kkeeper, keeper, eeper, eper, er, per, r] 

aber es funktioniert nicht, wenn ich so etwas wie "ATATATATATA" verwenden

├── (1) ATATATATATA 
└── (2) TATATATATA 

Suffixe:

[ATATATATATA, TATATATATA] 

Aber die richtige Suffixe sein sollte:

[A, ATA, ATATA, ATATATA, ATATATATA, ATATATATATA, TA, TATA, TATATA, TATATATA, TATATATATA] 

ich die Antwort, indem ich alle Suffixe jeden ‚Endknoten‘ String finden kann, aber das scheint nicht, wie der richtige Ansatz. Irgendwelche anderen Vorschläge?

EDIT: Dank izomorphius! Das Hinzufügen eines END_CHAR zur ursprünglichen Zeichenkette half einem Haufen.

├── (21) # 
├── (19) A 
│ ├── (20) # 
│ └── (15) TA 
│  ├── (16) # 
│  └── (11) TA 
│   ├── (12) # 
│   └── (7) TA 
│    ├── (8) # 
│    └── (3) TA 
│     ├── (4) # 
│     └── (1) TA# 
└── (17) TA 
    ├── (18) # 
    └── (13) TA 
     ├── (14) # 
     └── (9) TA 
      ├── (10) # 
      └── (5) TA 
       ├── (6) # 
       └── (2) TA# 

Suffixe:

[A, ATA, ATATA, ATATATA, ATATATATA, ATATATATATA, TA, TATA, TATATA, TATATATA, TATATATATA] 

Answer 1

Die typische Tipp, wie man ein Suffix-Baum zu bauen, ist ein künstlicher Charakter hinzufügen, die Sie wissen nicht im Alphabet ist. Normalerweise füge ich '#' hinzu und dann erstelle ich den Suffixbaum für ATATATATATA #, so dass du dieses Problem nicht mehr hast.

Sie erhalten das Problem, das Sie beschreiben, weil die fehlenden Suffixe tatsächlich als Präfixe eines anderen Suffixes erfüllt werden. Das Hinzufügen eines künstlichen Zeichens am Ende stellt sicher, dass dies niemals passieren wird.