AbstractWe 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.
Categories and Subject Descriptors: F.1.1 [Computation by Abstract Devices]: Models of Computation; F.2.0 [Analysis of Algorithms and Problem Complexity]; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; F.4.3 [Mathematical Logic and Formal Languages]: Formal Languages
Additional Key Words and Phrases: finite automata, pattern-matching, strings
Selected references
- Alfred V. Aho and David Lee. Storing a dynamic sparse table. In 27th Annual Symposium on Foundations of Computer Science, pages 55-60, Toronto, Ontario, Canada, 27-29 October 1986. IEEE.
- M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, and R. E. Tarjan. Dynamic perfect hashing: Upper and lower bounds. In 29th Annual Symposium on Foundations of Computer Science, pages 524-531, White Plains, New York, 24-26 October 1988. IEEE.
- Donald E. Knuth, James H. Morris, Jr., and Vaughan R. Pratt. Fast pattern matching in strings. SIAM Journal on Computing, 6(2):323-350, June 1977.