His regex golf seems kind of strange; he never mentions suffix trees. It seems like a fairly straightforward process to go through and mark the shortest distinguishing infix for each string in a generalized suffix tree.