> 我是刚学后缀树和后缀数组的。这道题我是先用 Ukkonen 算法构造的后缀树，然后再从后缀树得到后缀数组的。
> 
> 在后缀树中，如果用数组记录每个节点的子节点，我要用 60M 内存；如果用链表记录子节点，我要用 25M 内存。而且 Ukkonen 算法编码也蛮复杂的。
> 
> 我看到有好多人只用了几 M 的内存，不禁想问一下各位还有什么更好的构造后缀数组的算法吗。可以的话，请给一些网址或者书名、论文标题。谢谢。

• 谢谢，倍增算法果然很简炼，速度也可以。我又查到一个 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