Give an efficient algorithm for computing the transition function for the string matching automaton corresponding to a pattern P .

Your algorithm should run in time O(m||).

(Hint. Prove that (q , a) = ( [ q ] , a) if q = m or P[q + 1] = a.)