Making a NFA for accepting a string only if it contains the given substrings First I'll introduce the problem with just two substrings. Say you are asked to construct a NFA which accepts the input string if it has both "bb" and "aba" as substrings. 

The solution we came up with in class was that we'll make a NFA with multiple start states (a start state with $\epsilon$-transitions to each of our desired multiple start states). We'll have two cases, one where the substring "aa" occurs before the substring "aba" and one where the substring "aba" occurs before the substring "aa". 

Following is the NFA diagram:   



But the problem with that solution is that it doesn't generalize well (for example, now if I have to check that the given string contains 10 given strings as substrings, if I have to make a branch for every permutation, I'll have 10! branches). 

Is there a simpler solution to this where the complexity of the NFA to be drawn does not increase as factorial of the number of 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.