Matching of strings can be done by automata. The random string at the top is processed by the automaton shown in the graph. It implements recognition of the pattern to match. The automaton processes each input character once. Beginning and ending positions of matches are indicated at the bottom.