Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

http://baike.baidu.com/view/1240197.htm

Posted by 20053565 at 2008-02-25 19:14:06 on Problem 3415
In Reply To:请问各位是用什么算法构造后缀数组的。我看到好多人内存用得好少。 Posted by:ImLazy at 2008-02-25 14:23:39
> 我是刚学后缀树和后缀数组的。这道题我是先用 Ukkonen 算法构造的后缀树,然后再从后缀树得到后缀数组的。
> 
> 在后缀树中,如果用数组记录每个节点的子节点,我要用 60M 内存;如果用链表记录子节点,我要用 25M 内存。而且 Ukkonen 算法编码也蛮复杂的。
> 
> 我看到有好多人只用了几 M 的内存,不禁想问一下各位还有什么更好的构造后缀数组的算法吗。可以的话,请给一些网址或者书名、论文标题。谢谢。

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator