You can use a suffix tree, which is a compressed trie that allows you to store all possible suffixes from the strings in $S$. To search for a substring $q$, you can simply traverse the suffix tree from the root1 to the leaves, making comparisons with the edge keys (each of which represents one or more characters). If a branch does not exist in the tree, then $q$ is not a substring in $S$; otherwise, it is.
If you want to find out the exact string in $S$ that contains $q$, you can annotate the nodes of the suffix tree so that they contain this information (e.g., you can add a string number and a starting position). This is the idea generalized suffix trees are built upon.
The running time of this approach is $O(n \: l)$ for the construction of the suffix tree, plus $O(k)$ for the substring search, for a total of $O(n \:l + k)$.
1 Note that every substring of a string $T$ is the prefix of exactly one suffix of $T$. Therefore, substring search can always be performed starting at the root of a suffix tree.