Give an alphabet $\mathcal{A}=\{a_1,a_2,\ldots,a_m\}$, and let $L_n$ is the set of all possible $n$-length words in form $[a_{i_1}a_{i_2}a_{i_3}\ldots a_{i_n}],\ a_{i_j}\in \mathcal{A}$.
We call a $k$-covering of $L_n$ is a set $C$ with elements are $k$-length words, $k\le n$, such that every word from $L_n$ have at least a continuous part that is a word in $C$.
My question is what is the possible minimum size of a $k$-covering for $L_n$ (depends on $k, m, n$), and how many k-coverings for $L_n$ at all? The algorithm problem is also interesting about finding a $k$-covering with minimum size.
Another type of "$k$-covering" is also not trivial, with the same questions:
Give an alphabet $\mathcal{A}=\{a_1,a_2,\ldots,a_m\}$, and let $L_n$ is the set of all possible n-length words in form $[a_{i_1}a_{i_2}a_{i_3}\ldots a_{i_n}],\ a_{i_j}\in \mathcal{A}$.
We call a $k$-covering of $L_n$ is a subset $C$ of $L_n$, $k\le n$, such that every word from $L_n$ have at least a $k$-continuous part that is also a continuous part of some word in $C$, or we can say every $n$-length word $k$-match with some word in $C$.
Note: For more convenient in discussion, I call the first one "type I", and second one "type II" $k$-covering.
