Skip to Main content Skip to Navigation
Journal articles

On-line construction of position heaps

Abstract : We propose a simple linear-time on-line algorithm for constructing a position heap for a string [EMOW11]. Our definition of position heap differs slightly from the one proposed in [EMOW11] in that it considers the suffixes ordered in the descending order of length. Our construction is based on classic suffix pointers and resembles Ukkonen's algorithm for suffix trees [Ukk95]. Using suffix pointers, the position heap can be extended into the augmented position heap that allows for a linear-time string matching algorithm [EMOW11].
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00790301
Contributor : Gregory Kucherov <>
Submitted on : Tuesday, February 19, 2013 - 5:33:12 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM

Links full text

Identifiers

Citation

Gregory Kucherov. On-line construction of position heaps. Journal of Discrete Algorithms, Elsevier, 2013, 20 (May), pp.3-11. ⟨10.1016/j.jda.2012.08.002⟩. ⟨hal-00790301⟩

Share

Metrics

Record views

245