  Given a set of strings, the shortest common superstring problem is to find
the shortest possible string that contains all the input strings. The problem
is NP-hard, but a lot of work has gone into designing approximation algorithms
for solving the problem. We present the first time and space efficient
implementation of the classic greedy heuristic which merges strings in
decreasing order of overlap length. Our implementation works in $O(n \log
\sigma)$ time and bits of space, where $n$ is the total length of the input
strings in characters, and $\sigma$ is the size of the alphabet. After index
construction, a practical implementation of our algorithm uses roughly $5 n
\log \sigma$ bits of space and reasonable time for a real dataset that consists
of DNA fragments.
