ONLINE CONSTRUCTION OF SUFFIX TREES
ONLINE CONSTRUCTION OF SUFFIX TREES
复制标题
DOI：
10.1007/bf01206331
复制
发表时间：
1995-09-01
期刊：
影响因子：
1.1
通讯作者：
UKKONEN, E
中科院分区：
文献类型：
--
作者：
UKKONEN, E
本文提出了一种在线算法，用于构造给定字符串的后缀树，该后缀树在时间上与字符串的长度成线性关系。新算法具有从左到右逐符号处理字符串的理想特性。它总是为字符串的扫描部分准备好后缀树。该方法被开发为一个非常简单的算法（二次大小）后缀尝试的线性时间版本。不管它的二次最坏情况下，后一种算法可以是一个很好的实用方法时，字符串不是太长。这种方法的另一种变体是给出，以自然的方式，著名的算法构造后缀自动机（DAWG）。
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 always has 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, ina natural way, the well-known algorithms for constructing suffix automata (DAWGs).