1973 年 Weiner 给出了后缀树的第一个线性时间构造。该算法于 1976 年由 McCreight 和 1995 年由 Ukkonen 简化。尽管如此，我发现 Ukkonen 的算法在概念上相对复杂。
自 1995 年以来，Ukkonen 的算法是否有过简化？
问问题
543 次
2 回答
2
对原始问题的更直接的答案是 Giegerich、Kurtz、Stoye 的自上而下（和惰性）后缀树构造：https ://pub.uni-bielefeld.de/luur/download?func=downloadFile&recordOId=1610397&fileOId=2311132
此外，后缀数组（如上一个答案中所述）不仅更容易构建，而且可以增强它们以模拟您对后缀树的期望：http ://www.daimi.au.dk /~cstorm/courses/StrAlg_e04/papers/KurtzOthers2004_EnhancedSuffixArrays.pdf
由于可以压缩增强后缀数组中涉及的数据结构，因此可以压缩（模拟）后缀树：http ://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.8644&rep=rep1&type=pdf
于 2012-02-18T13:44:45.837 回答
1
这不是一个直接的答案，但它可以帮助你。
去年，在研究这个主题时，我结束了使用 suffix-arrays 而不是 suffix-trees，而 IIRC，我使用了论文“An incomplex algorithm for fast suffix array construction” KB Schürmann (2007) [1] 作为参考。IIRC，它是构建后缀数组的两遍线性算法。
于 2012-02-17T16:09:29.747 回答