deterministic finite automaton for "does contain substring $w$" is of linear size
Consider the following NFA: the states are $q_0,\ldots,q_{|w|}$, there are transitions $q_{i-1} \to q_i$ on $w_i$, there are self-loops on $q_0,q_{|w|}$ (for all alphabet symbols), the initial state is $q_0$, and the unique final state is $q_{|w|}$.

Assuming $w \neq \epsilon$, the determinization generates $2|w|$ states:


For each location $0 \leq i &lt; |w|$, a state consisting of $q_0$, $q_i$, and $q_j$ for $j &lt; i$ such that $w_1\ldots w_j$ is a suffix of $w_1\ldots w_i$.
Same as before, with $q_{|w|}$ added.


When $w = \epsilon$, the NFA is already deterministic, and contains only one state.