Résumé
The hierarchical overlap graph (HOG for short) is an overlap encoding graph that efficiently represents overlaps from a given set P of n strings. A previously known algorithm constructs the HOG in O(||P || + n 2) time and O(||P || + n × min(n, max{|s| : s ∈ P })) space, where ||P || is the sum of lengths of the n strings in P. We present a new algorithm of O(||P || log n) time and O(||P ||) space to compute the HOG, which exploits the segment tree data structure. We also propose an alternative algorithm using O(||P || log n log log n) time and O(||P ||) space in the word RAM model of computation.