The string-matching automaton is very efficient: it examines each character in the text exactly once and reports all the valid shifts in O(n) time.

The basic idea is to build a automaton in which

• Each character in the pattern has a state.

• Each match sends the automaton into …