In shortest superstring problem we have set of words, we want to find shortest string containing all given words
Shortest Superstring is solved by greedy algorithm. First we remove all repeat words, and proper substring of other words. Then we merge pair of words with maximum overlap until 1 words left.
example file is shortest_superstring_example.cpp
O(max(n,k)) n is size of input k is size max letter in alphabet
The algorithm is described in the