  The hierarchical overlap graph (HOG) is a graph that encodes overlaps from a
given set P of n strings, as the overlap graph does. A best known algorithm
constructs HOG in O(||P|| log n) time and O(||P||) space, where ||P|| is the
sum of lengths of the strings in P. In this paper we present a new algorithm to
construct HOG in O(||P||) time and space. Hence, the construction time and
space of HOG are better than those of the overlap graph, which are O(||P|| +
n^2).
