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.

Improve this question
$\endgroup$
4
  • $\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 ♦
    Commented Mar 4, 2019 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
    Commented Mar 4, 2019 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 ♦
    Commented Mar 4, 2019 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
    Commented Mar 4, 2019 at 22:04

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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