Skip to Main content Skip to Navigation
Conference papers

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 the 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].
Document type :
Conference papers
Complete list of metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00681855
Contributor : Gregory Kucherov <>
Submitted on : Thursday, March 22, 2012 - 4:08:23 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM
Long-term archiving on: : Saturday, June 23, 2012 - 2:36:07 AM

File

paper.pdf
Files produced by the author(s)

Identifiers

Citation

Gregory Kucherov. On-Line Construction of Position Heaps. 18th International Symposium on String Processing and Information Retrieval (SPIRE 2011), Oct 2011, Pisa, Italy. pp.326-337, ⟨10.1007/978-3-642-24583-1_32⟩. ⟨hal-00681855⟩

Share

Metrics

Record views

304

Files downloads

331