n South African Computer Journal - Algorithms for the shortest exact common superstring problem

Volume 2000, Issue 26
  • ISSN : 1015-7999
  • E-ISSN: 2313-7835



The Shortest Exact Common Superstring (SECS) problem is: Given a set of strings f = {w1; w2; : : :;wn}, where no wi is an exact substring of wj , i ≠j, find a shortest string Se such that every string of f is an exact substring of Se. When the number of the strings n > 2, the SECS problem becomes NP-complete. In this paper, we present an exact SECS algorithm and a greedy approximation one. Our greedy algorithm is a1/2-approximation for the SECS problem. Our exact SECS algorithm and our greedy one are, respectively, of complexities O(n n ) and O(n 2 (l +log(n))) in computing time, where n is the number of the strings and l is the maximum length of a string. Our SECSalgorithms are based on the computation of the Length of the Exact Longest Overlap (LELO).

Loading full text...

Full text loading...


Article metrics loading...


This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error