On-line algorithms for k-Covering
Costas S. Iliopoulos, W.F. Smyth · Murdoch Research Repository (Murdoch University) · 1998
An O(n2(n-k)) on-line algorithm for computing a minimum set of k-covers for a given string of length n is presented. A straightforward modification of the algorithms yields O(kn2(n-k)) algorithms for computing a minimum set of k-covers and k-segments for a given circular string of length n. We show further that the number of such minimum sets of k-covers may be exponential. Similar time complexity bounds hold for computing the minimum sets of k-segments and k-seeds.