Shortest string which all input strings is its substring

Question

Given a set of input strings, how do I find a shortest string S so that all input strings appear as a substring of S?

for example:

foobar + bar -> foobar
foo + bar + rfo -> barfoo

I guess it's related to graphs, but don't know how to solve it.

1. first check all the "substrings", for example, "bar" to "foobar". Remove "bar".
2. the more two string share head and tail, the more likely they will be joined together, like nodes in a graph.

---

background:

GCC seems to do an optimization where it combines string literals that share the same suffix.

https://stackoverflow.com/questions/51551068/

So I want to broaden this problem.

• Nathaniel: What did you try?
• D.W.: Please edit your post to specify the problem more precisely. Please define what "includes" means. Does it mean as a substring (consecutively?) or as a subsequence (letters not necessarily consecutive)? Where did you encounter this problem?
• D.W.: Please state the problem in the body of the post. Reading the body of the post (without reading the title), it should make sense. The title is not just the first sentence of the body of the post.

Answer 1

This is called the shortest common superstring problem. It is NP-hard. Therefore, you should not expect any efficient algorithm that works for all possible inputs.

Like many NP-hard problems, I imagine you could solve it with a SAT solver or ILP solver, or use an approximation algorithm (see the Wikipedia article for one approximation algorithm).