On-line construction of position heaps

Gregory Kucherov

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)


We propose a simple linear-time on-line algorithm for constructing a position heap for a string (Ehrenfeucht et al., 2011 [8]). Our definition of position heap differs slightly from the one proposed in Ehrenfeucht et al. (2011) [8] 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 (Ukkonen, 1995 [17]). Using suffix pointers, the position heap can be extended into the augmented position heap that allows for a linear-time string matching algorithm (Ehrenfeucht et al., 2011 [8]).

Original languageEnglish
Pages (from-to)3-11
Number of pages9
JournalJournal of Discrete Algorithms
Publication statusPublished - May 2013
Externally publishedYes


  • Data structures
  • Position heap
  • String algorithms
  • Text index


Dive into the research topics of 'On-line construction of position heaps'. Together they form a unique fingerprint.

Cite this