Before revision:  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 cummulative sum of the lengths of strings in P.
After revision:  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.