Fast and Practical Algorithms for Computing All the Runs in a String
Fast and Practical Algorithms for Computing All the Runs in a String
复制标题
用于计算字符串中所有运行的快速实用算法
DOI：
10.1007/978-3-540-73437-6_31
复制
发表时间：
2007
影响因子：
1.4
通讯作者：
W. F. Smyth
中科院分区：
文献类型：
--
作者：
Gang Chen;S. Puglisi;W. F. Smyth
字符串x中的重复是x的子串w = ue，最大e ≥ 2，其中u本身不是w中的重复。x中的游程是“最大周期性”的子串w = ueu*，其中ue是重复，u* 是u的最大长度可能为空的固有前缀。一次运行可以编码多达|u|重复任何字符串x = x[1...]中的最大重复次数。n]是已知的Θ（nlog n）。在2000年，Kolpakov和Kucherov证明了x中的最大运行次数是O（n）;他们还描述了一个基于Farach的Θ（n）-时间后缀树构造算法（STCA）、Θ（n）-时间Lempel-Ziv分解和Main的Θ（n）-时间最左运行算法的Θ（n）-时间算法，来计算x中的所有运行。最近Abouelhoda等人提出了一种基于“增强型”后缀数组的Θ（n）时间Lempel-Ziv分解算法--后缀数组与其他支持数据结构一起。在本文中，我们介绍了一个快速的空间有效的算法来计算所有的运行在一个字符串，出现在许多情况下是上级那些以前提出的。
A repetition in a string x is a substring w = ue of x, maximum e ≥ 2, where u is not itself a repetition in w. A run in x is a substring w = ueu* of "maximal periodicity", where ue is a repetition and u* a maximum-length possibly empty proper prefix of u. A run may encode as many as |u| repetitions. The maximum number of repetitions in any string x = x[1..n] iswell known to be Θ(n log n). In 2000 Kolpakov & Kucherov showed that the maximum number of runs in x is O(n); they also described a Θ(n)-time algorithm, based on Farach's Θ(n)-time suffix tree construction algorithm (STCA), Θ(n)-time Lempel-Ziv factorization, and Main's Θ(n)-time leftmost runs algorithm, to compute all the runs in x. Recently Abouelhoda et al. proposed a Θ(n)-time Lempel-Ziv factorization algorithm based on an "enhanced" suffix array -- a suffix array together with other supporting data structures. In this paper we introduce a collection of fast space-efficient algorithms for computing all the runs in a string that appear in many circumstances to be superior to those previously proposed.