This question already has an answer here:

Let's say that we have the strings Hello, World, Hello and World. The algorithm I am thinking of would create an immutable buffer that contains Hello, World and the previous three would then become references or slices of that one like buf[0,11], buf[0,4], buf[7,11].

A way to implement this algorithm would be to compare all new strings to the existing buffer and reuse it if possible or append the new string if that's not the case. This would be very slow, but it should work. However, it does not efficiently handle a case like Hey, Hello because it would either append it to the buffer, adding Hello again, or add Hey, to the beginning and update all the indices.

If saving space is the optimal solution, then the final buffer would be Hey, Hello, World.

Is there any algorithm that does something similar?

I have read about ropes, and read this article, but I do not see how these would help.

EDIT: this is indeed a shortest superstring problem, but the implementations I have found (1,2) assume that no string in the array could be a substring of another one, which is not the case here.


marked as duplicate by xskxzr, Evil, dkaeae, vonbrand, Yuval Filmus Sep 2 at 13:24

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ @xskxzr they are very, very similar, but this one has the twist that there can be substrings of other strings in the array $\endgroup$ – Armando H. Aug 24 at 5:08
  • $\begingroup$ If you just need references to an array, use a language or library with support for slices-as-views $\endgroup$ – D. Ben Knoble Aug 24 at 18:41
  • $\begingroup$ The issue was constructing a superstring from all those strings. The slice part is already implemented. $\endgroup$ – Armando H. Aug 24 at 20:33

It is a shortest superstring problem and not allowing internal substrings is just an implementation detail.


Not the answer you're looking for? Browse other questions tagged or ask your own question.