An Algorithm for a Modification of the Shortest Common Superstring Problem

The purpose of this study is to develop an efficient algorithm to solve a variation of the NP-hard Shortest Common Superstring (SCS) problem. In this version of the problem, one string is allowed to have up to K mistakes, meaning it does not match the SCS in at most K places. Also, there is a slight constraint on the problem in that no string can be a substring of another. The algorithm proposed is exact, not an approximation, meaning it finds the best answer in all cases.