String-Matching with Automata.
Mehryar Mohri · 1997
. We present an algorithm to search in a text for the patterns of a regular set. Unlike many classical algorithms, we assume that the input of the algorithm is a deterministic automaton and not a regular expression. Our algorithm is based on the notion of failure function and mainly consists of efficiently constructing a new deterministic automaton. This construction is shown to be efficient. In particular, its space complexity is linear in the size of the obtained automaton. Key words: Finite automata, pattern-matching, strings. CR Classification: F.1.1, F.2.0, F.2.2, F.4.3 1. Introduction Pattern-matching consists of finding the occurrences of a set of strings in a text. Two general approaches have been used to perform this task given a regular expression r describing the patterns. Both require a preprocessing stage, which consists of constructing an automaton representing the set described by the regular expression A r, where A is the alphabet of the text. This automaton is th...