# Find the smallest set of strings which “covers” a given set of strings (coverage = containing as substring)

Let $$S$$ be a finite set of strings and $$0 < k\leq l$$ integers. We want to find the smallest set of strings $$T(k,l)$$ for which the following holds:

• $$\forall t \in T(k,l): k \leq |t| \leq l$$
• $$\forall s \in S \ \exists t \in T(k,l): t \subset s$$ (meaning: $$s$$ is containing $$t$$ as a contiguous substring).

I would appreciate any help regarding this problem. I see that I could generate the set of all strings with length between $$k$$ and $$l$$ then consider the power set but I think there must be a better way to solve this.

I'm not even sure how hard this problem is (I think there may be a reduction for the set cover problem which means it is $$NP$$-complete but I really don't know) or if there are any good approximation (or maybe exact) algorithms available.

I would like to solve this problem primarily in practice. Typically, $$3 \leq k \leq l \leq 10$$ holds, $$|S| \approx 2000$$ and the lengths of the elements in $$S$$ can vary from 10 to 50 mainly.

• This problem appears to be a generalization of the longest common substring problem. There is a lot of literature on the related longest common sub sequence problem (which is NP-hard), but I'm having a hard time finding similar results for the substring version. (which I also believe to be hard) – Discrete lizard Mar 4 at 12:46
• Surely k doesn't affect the problem in any way: if you can do this with T containing a string of length less than k then you can just pad that string to have length k... – Daniel McLaury Mar 4 at 13:38
• @DanielMcLaury You mean $l$, right? We are looking for a sub string, so we cannot just pad the elements in T. We can, of course, make them smaller. – Discrete lizard Mar 4 at 14:55
• Approximation algs for this problem are discussed in Vijay Vazirani's text on approximation algorithms. books.google.com/… – Neal Young Mar 4 at 22:04

Without loss of generality, we can take $$l=k$$. In particular, any solution to $$T(k,l)$$ can be converted into a solution for $$T(k,k)$$ by shortening each string that's longer to $$k$$ to a string of length $$k$$ (by deleting as many characters from the beginning or end as needed to get down to length $$k$$, chosen arbitrarily). So, it will simplify your life to focus on solving $$T(k,k)$$, i.e., finding a set of strings of length $$k$$.
Here is one possible approach. You don't need to exhaustively generate all strings of length $$k$$. Instead, you can generate all length-$$k$$ substrings of words of $$S$$. If each word of $$S$$ has length $$\le n$$, then there will be $$\le (n-k+1) \cdot |S|$$ of them. Then, you could apply some standard set-cover algorithm to that. So, you don't need to generate exponentially many strings; just polynomially many.