Given $s$ as a string over some alphabet, what is the best known algorithm to compute a corresponding deterministic finite-state automaton (DFA) that accepts any string that contains $s$?
I am mostly interested of the lowest time complexity so if you tell me what is the best known complexity in O notation to build an automaton for a string that would be just as good.
Hendrik Jan is correct about the Knuth-Morris-Pratt 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:
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.
Answer. Although I have seen a deleted answer, I still think the construction is linear in the length of the string (considering the alphabet size constant). Aho Corasick 1975, doi:10.1145/360825.360855
Or perhaps KMP. Aho & Corasick consider pattern matching automata for a finite set of words, forming a tree with back-pointers in case of mismatches=failures. This is in the style of the Knuth-Morris-Pratt algorithm, that considers a single string. I could not find whether KMP actually explicitly move from match/failure automata to the deterministic automata (with a transition for every letter in the alphabet). Thus basically the KMP approach suffices together with a clever argument that this can be turned into a DFA in linear time. A&C explicitly mention that last step. The KMP failure table however is slightly simpler than the A&C construction (one does not need a tree of strings) and can be found all over the web.
A note. Anyone interested in pattern matching should read the original KMP paper, doi: 10.1137/0206024, or at least the historical remarks from Section 7. Quote: "Knuth was chagrined to learn that Morris had already discovered the algorithm, without knowing Cook’s theorem [..]". The KMP paper was published only in 1977 while Morris already implemented his version in a text-editor in 1969, while Knuth and Pratt discovered their slighly later as an application of a proof of Cook.
