The shortest superstring problem, often abbreviated SSP, is a computational problem whose answer is the shortest string which contains each string from a given set of strings. In other words it is a problem involved with finding a superstring, a string containing each member of a set of strings in order, of minimum length. The shortest superstring problem has applications in data compression, sparse matrix compression, and computational biology, namely DNA-sequencing. It is a pure classical optimization problem.

An example of the shortest superstring problem is as follows: Given a collection of strings S={s₁, s₂..., s_n} over a finite alphabet find the shortest superstring that contains each s_i as a substring.

• s₁ = babab
• s₃ = abcba
• s₂ = ababc
• s₄ = babca

In this case = abcbababca and is ten characters long.

Undoubtedly two of the most common applications of the shortest superstring problem are...