我是刚学后缀树和后缀数组的。这道题我是先用 Ukkonen 算法构造的后缀树，然后再从后缀树得到后缀数组的。

在后缀树中，如果用数组记录每个节点的子节点，我要用 60M 内存；如果用链表记录子节点，我要用 25M 内存。而且 Ukkonen 算法编码也蛮复杂的。

我看到有好多人只用了几 M 的内存，不禁想问一下各位还有什么更好的构造后缀数组的算法吗。可以的话，请给一些网址或者书名、论文标题。谢谢。

• 后缀树，好恐怖~~ 就用倍增算法就好了，才20几行代码.. (218) richardxx 2008-02-25 14:29:06
• http://baike.baidu.com/view/1240197.htm (218) 20053565 2008-02-25 19:14:06
  • 谢谢，倍增算法果然很简炼，速度也可以。我又查到一个 DC3 算法，O(3n) 的，编码也不是很烦。在以下网址。 (213) ImLazy 2008-03-07 20:47:07
    • 嗯，这个论文早看到，很赞。。。 (221) sunny_fable 2008-03-07 21:25:32
    • 啊，大牛把DC3都搞定啦？？写篇帖子教教我们吧~ (221) richardxx 2008-03-07 22:54:29
      • 我没什么可教的，我只是照论文上的做而已。 (0) ImLazy 2008-03-09 23:11:54
    • 看不懂啊！！！e语不好，谁能翻译成中文吗？ (221) swust20064469 2008-12-13 21:18:18
• Re:请问各位是用什么算法构造后缀数组的。我看到好多人内存用得好少。 (226) Felicia 2008-02-26 11:28:37