我已经基于这里的站点http://marknelson.us/1996/08/01/suffix-trees/在Java中构建了一个后缀树但是我've run into a problem. I can build a suffix tree fine but I can trying to build a set of all suffixes from the tree. I basically find all the '结束节点' and return the string which is represented by that '结束节点'
该算法适用于像“簿记员”这样的单词
├── (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]
我可以通过查找每个“结束节点”字符串的所有后缀来找到答案，但这似乎不是正确的方法 . 还有其他建议吗？
编辑：谢谢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]
1 回答
关于如何构建后缀树的典型提示是添加一个您知道不在字母表中的人工角色 . 我通常添加'＃'然后我为ATATATATATA＃构建后缀树，这样你就不会再遇到这个问题了 .
您得到了您描述的问题，因为缺少的后缀实际上被视为另一个后缀的前缀 . 最后添加一个人工角色可确保永远不会发生这种情况 .