  Genome assembly is a fundamental problem in Bioinformatics, where for a given
set of overlapping substrings of a genome, the aim is to reconstruct the source
genome. The classical approaches to solving this problem use assembly graphs,
such as de Bruijn graphs or overlap graphs, which maintain partial information
about such overlaps. For genome assembly algorithms, these graphs present a
trade-off between overlap information stored and scalability. Thus,
Hierarchical Overlap Graph (HOG) was proposed to overcome the limitations of
both these approaches.
  For a given set $P$ of $n$ strings, the first algorithm to compute HOG was
given by Cazaux and Rivals [IPL20] requiring $O(||P||+n^2)$ time using
superlinear space, where $||P||$ is the cumulative sum of the lengths of
strings in $P$. This was improved by Park et al. [SPIRE20] to $O(||P||\log n)$
time and $O(||P||)$ space using segment trees, and further to
$O(||P||\frac{\log n}{\log \log n})$ for the word RAM model. Both these results
described an open problem to compute HOG in optimal $O(||P||)$ time and space.
In this paper, we achieve the desired optimal bounds by presenting a simple
algorithm that does not use any complex data structures. At its core, our
solution improves the classical result [IPL92] for a special case of the All
Pairs Suffix Prefix (APSP) problem from $O(||P||+n^2)$ time to optimal
$O(||P||)$ time, which may be of independent interest.
