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 a new state.

• If all the characters in the pattern has been matched, the automaton enters the accepting state.

• Otherwise, the automaton will return to a suitable state according to the current state and the input character such that this returned state reflects the maximum advantage we can take from the previous matching.

• the matching takes O(n) time since each character is examined once. The construction of the string matching automaton is based on the given pattern. The time of this construction may be O(m3 |S|)

The finite automaton begins in state q0 and read the characters of its input string one at a time. If the automaton is in state q and reads input character a, it moves from state q to state δ(q,a).

Finite automata: A finite automaton M is a 5-tuple (Q,q0 ,A,S,d), where

• Q is a finite set of states.

• q0  Q is the start state.

• A  Q is a distinguish set of accepting states.

• S is a finite input alphabet

• d is a function from Q × S into Q, called the transition function of M.