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.