サフィックスツリーからサフィックスを生成する

Question

ここではサイトに基づいてJavaでサフィックスツリーを構築しましたが、これはhttp://marknelson.us/1996/08/01/suffix-trees/ですが、問題が発生しました。私はサフィックスツリーをうまく構築できますが、ツリーからすべてのサフィックスを作成しようとすることができます。私は基本的にすべての「エンドノード」を見つけて、その「末端ノード」によって表現された文字列を返すことをアルゴリズムは、「簿記」

├── (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 

サフィックスのように単語のために働く

：

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

しかし、私は "ATATATATATA"

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

サフィックスようなものを使用する場合、それは失敗します。

[ATATATATATA, TATATATATA] 

しかし、適切な接尾辞は次のようになります。

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

私は、各「エンド・ノードの文字列のすべてのサフィックスを見つけることによって答えを見つけることができますが、それはその正しいアプローチのように見えるしていません。その他の提案はありますか？

EDIT： ありがとうizomorphius！元の文字列にEND_CHARを追加すると束になりました。

├── (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# 

サフィックス：

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

Answer 1

接尾辞木を構築する方法についての一般的なヒントは、あなたが知っているアルファベットにはない1つの以上の人工文字を追加することです。私は通常 '＃'を追加して、ATATATATATAのサフィックスツリーを構築します。＃このようにすれば、この問題はもう発生しません。

欠落している接尾辞が別の接尾辞の接頭辞として実際に満たされているため、問題の説明があります。最後に人工的な文字を追加することは、これが決して起こらないことを保証する。