Hendrik Jan is correct about the [Knuth-Morris-Pratt algorithm](http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm) (warning, wikipedia doesn't explain it particularly well, a text on algorithms is probably a better bet). The failure function can be used to extract a DFA that can perform the string matching. It's not immediately obvious that the failure table is a DFA, but with very little work the transition table for the DFA can be constructed. If $W$ is the pattern string you want to match, the time to build the table (and hence construct the DFA) is $O(|W|)$.

The central idea is that the failure table $T$ (I'll try to use the same names as wikipedia, just to get a ready-made example) tells you where you could be up to in the string if the current match doesn't work out, i.e. if you don't see the next character you're expecting, perhaps the beginning of the match you want has already been seen, you're just mistakenly further ahead, so you only want to "back-track" a little (note, there's no real backtracking in the usual algorithmic sense).

So, shamelessly stealing the example from wikipedia, say we have the failure table $T$:

$$\begin{array}{c|cccccc}
i & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\\hline
W[i] & A & B & C & D & A & B & D \\
T[i] & -1 & 0 & 0 & 0 & 0 & 1 & 2
\end{array}
$$


We can construct the DFA as follows; we have $|W|+1$ states, with a backbone of transitions that match the entire pattern. To match the table we'll call the start state $q_{-1}$ and the final state $q_{|W|}$ (so in the example $q_{6}$). The backbone is then the transitions $\delta(q_{i-1},W[i]) = q_{i}$, so in the example, we go from the start state $q_{-1}$ to state $q_{0}$ on an $A$ and from $q_{2}$ to $q_{3}$ on a $D$.

Now the trick is to add the correct "backwards" transitions so that we don't go too far back along the backbone when we get something wrong. This is where we us the failure function. If we're in state $q_{i-1}$ and we don't see $W[i]$ as the next symbol, then we can alternatively transition to $q_{T[i]}$ if we see $W[T[i]]$. From the example, if we're in state $q_{5}$, and we don't see a $D$, but we do see a $C$, we can go to $q_{2}$. Every other symbol returns us to the start state.

Reiterating; there are three types of transitions, the backbone transition if everything's going fine, the transition given by the failure table so we might be able to recover a bit, and $|\Sigma| - 2$ other transitions that take us back to the start state.

The start and final states are a little special of course, the start state can't go back further, so the failure recovery transition appears with the other transitions, and once we reach the final state, it doesn't matter what else we see, so it's a sink state too.

There's one final wrinkle, the case where the failure symbol is the same as the expected (e.g. $W[1]$ and $W[5]$) in this case we can just defer the decision until they're different, or we can create an NFA.

The example then results in a DFA that looks (barring mistakes) like:

![DFA resulting from failure table example.][1]

The dashed transitions represent the "everything left over" transitions.

It should be easy enough to see that given the table, we can construct the DFA in $O(|W|)$ time (in one pass really). The table can also be constructed in $O(|W|)$ time - the source code on wikipedia is sufficient. If we get clever, of course we can skip the intermediate table step and use the table building algorithm to just create the DFA immediately. This running time is also the best we can hope for, as a DFA that matches only this string has to have at least $|W|$ transitions (and $|W|+1$ states), so we need to read the entire string $W$, which takes $\Omega(|W|)$ steps.


  [1]: https://i.sstatic.net/pMlzb.png