[HTML][HTML] On-line construction of position heaps
G Kucherov - Journal of Discrete Algorithms, 2013 - Elsevier
Journal of Discrete Algorithms, 2013•Elsevier
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 …
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 …
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]).
Elsevier