1.7.9 Shortest Common Superstring

Input Description: A set of strings s_1, ..., s_m. Problem: Find the shortest string S which contains each s_i as a substring of S. Excerpt from The Algorithm Design Manual: Shortest common superstring arises in a variety of applications, including sparse matrix compression. Suppose we have an n X m matrix with most of the elements being zero. We can partition each row into m/k runs of k elements

[Hash]

部分配列の集合から全体を組み立てる