Snowdream

I'm awake but my world is half asleep
posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

后缀树的在线生成算法

Posted on 2007-11-07 21:08 ZelluX 阅读(1731) 评论(1)  编辑  收藏 所属分类: Algorithm
第一次接触后缀树应该是在某次省队集训,徐串大牛做的讲座。
不过当时只是有了个印象。
现在发现这东东还是很好用的  @,@

http://www.blogjava.net/Files/zellux/SuffixT1withFigs.rar

On–line construction of suffix trees
by Esko Ukkonen

Key Words.
Linear time algorithm, suffix tree, suffix trie, suffix automaton, DAWG.

Abstract.
An on–line algorithm is presented for constructing the suffix tree for a given string in time linear in the length of the string. The new algorithm has the desirable property of processing the string symbol by symbol from left to right. It has always the suffix tree for the scanned part of the string ready. The method is developed as a linear–time version of a very simple algorithm for (quadratic size) suffix tries. Regardless of its quadratic worst-case this latter algorithm can be a good practical method when the string is not too long. Another variation of this method is shown to give in a natural way the well–known algorithms for constructing suffix automata (DAWGs).


评论

# re: 后缀树的在线生成算法  回复  更多评论   

2008-03-18 03:21 by ss
100101

只有注册用户登录后才能发表评论。


网站导航: