3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Discrete lizard Mar 4 at 12:46
  • 1
    $\begingroup$ 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... $\endgroup$ – Daniel McLaury Mar 4 at 13:38
  • 1
    $\begingroup$ @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. $\endgroup$ – Discrete lizard Mar 4 at 14:55
  • 2
    $\begingroup$ Approximation algs for this problem are discussed in Vijay Vazirani's text on approximation algorithms. books.google.com/… $\endgroup$ – Neal Young Mar 4 at 22:04
2
$\begingroup$

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.

It's possible there may be better algorithms that take into account the combinatorial structure of the strings; I don't know.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.