从后缀树生成后缀

我已经基于此处的网站构建了一个基于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]

我可以找到通过找出每个“端节点”字符串的所有后缀的答案，但似乎并不像正确的做法。还有其他建议吗？编辑：谢谢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]

来源

2012-04-09 Justin

看起来你的树没有完成'ATATATATATA'。 – Howard 2012-04-09 13:53:27

关于如何建立一个后缀树是多加一个人工字符，你知道是不是在字母表中的典型尖。我通常添加'＃'，然后为ATATATATATA＃构建后缀树，这样您就不会再遇到这个问题了。

你得到你描述的问题，因为缺失的后缀实际上是作为另一个后缀的前缀被满足的。在最后添加一个人造角色可确保这绝不会发生。

来源

2012-04-09 13:54:18

啊。感谢后缀 - >前缀连接。这现在非常合理。 – Justin 2012-04-09 14:04:56

从后缀树生成后缀

回答

相关问题