Example

$ \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} $

$\sa{1}\,\sa{2}\,\sa{6}\,\sa{3}\,\sa{9}\,\sa{2}\,\sa{3}\,\sa{7}\,\sa{5}\,\sa{7}$ is a shortest common superstring for the set of seven words $\{\sa{1}\,\sa{2}, \sa{2}\,\sa{3}, \sa{2}\,\sa{6}, \sa{5}\,\sa{7}, \sa{6}\,\sa{3}, \sa{7}\,\sa{5}, \sa{9}\,\sa{2}\}$.

Problem 62: Shortest Common Superstring of Short Words

A common superstring of a set $X$ of words is a word in which all elements of $X$ occur as factors. Computing a shortest common superstring (SCS) is an NP-complete problem but there are simple cases that can be solved efficiently, like the special case discussed in the problem.

Show how to compute in linear time the length of a shortest common superstring of a set $X$ of words of length $2$ over an integer alphabet.

Transform the question into a problem on graphs.

References

J. Gallant, D. Maier, and J. A. Storer. On finding minimal length superstrings. Journal of Computer and System Sciences, 20(1):50-58, 1980.

125 Problems in Text Algorithms

Example

Problem 62: Shortest Common Superstring of Short Words

References