Making a NFA for accepting a string only if it contains the given substrings
Given an alphabet $\Sigma = \{\sigma_1,\ldots,\sigma_n\}$, let us consider the problem of matching all strings which contain all of the letters as substrings, i.e. all the strings $\sigma_1,\ldots,\sigma_n$ as substrings. An NFA with $N$ states accepting this language can be converted to a context-free grammar in Chomsky normal form of size $O(nN)$ (this is the total size of all rules). It is known that any context-free grammar in Chomsky normal form for this language must have exponential size $\tilde{\Omega}((3/2^{2/3})^n)$ (see Theorem 9 here; we gain a quadratic factor since our grammar is in CNF), and so $N = \tilde{\Omega}((3/2^{2/3})^n)$.

Note that this is only an exponential lower bound, whereas the obvious construction has factorial complexity. However, you can improve on this construction. Given $n$ words, the idea is to guess which $n/2$ words will appear first and which $n/2$ words will appear last, and to recurse on each half. We obtain the recurrence
$$ T(n) = \binom{n}{n/2}\cdot 2T(n/2) \leq 2^n T(n/2). $$
Expanding the recurrence and using a trivial base case $T(1) = 1$, we get
$$
T(n) \leq 2^{n+n/2+\cdots} &lt; 4^n,
$$
which is only exponential. In actuality, $T(1)$ is the size of the largest word to be matched, so the bound above should be multiplied by that.