Shortest Superstring

Problem definition.

In shortest superstring problem we have set of words, we want to find shortest string containing all given words

Solution

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

#include "paal/greedy/shortest_superstring/shortest_superstring.hpp"

#include <iostream>
#include <string>

int main() {
    std::vector<std::string> words({ "ba", "ab", "aa", "bb" });

    std::cout << paal::greedy::shortestSuperstring(words) << std::endl;
}

example file is shortest_superstring_example.cpp

Approximation Ratio is 3.5, but is conjecture that is 2.

Complexity

O(max(n,k)) n is size of input k is size max letter in alphabet

References

The algorithm is described in the [9]