On finding minimal length superstrings

摘要

A superstring of a set of strings {s1,…, sn} is a string s containing each si, 1 ⩽ i ⩽ n, as a substring. The superstring problem is: Given a set S of strings and a positive integer K, does S have a superstring of length K? The superstring problem has applications to data storage; specifically, data compression. We consider the complexity of the superstring problem. NP-completeness results dealing with sets of strings over both finite and infinite alphabets are presented. Also, for a restricted version of the superstring problem, a linear time algorithm is given.