Efficient string matching
Alfred V. Aho, Margaret J. Corasick · Communications of the ACM · 1975
This paper describes a simple, efficient algorithm to locate all occurrences of any of a finite number of keywords in a string of text. The algorithm consists of constructing a finite state pattern matching machine from the keywords and then using the pattern matching machine to process the text string in a single pass. Construction of the pattern matching machine takes time proportional to the sum of the lengths of the keywords. The number of state transitions made by the pattern matching machine in processing the text string is independent of the number of keywords. The algorithm has been used to improve the speed of a library bibliographic search program by a factor of 5 to 10.
Cited by 2,944 works. doi:10.1145/360825.360855
Authors
References
- The Design and Analysis of Computer Algorithms
- Finite Automata and Their Decision Problems
- Sorting and Searching
- Switching and Finite Automata Theory
- Fundamental Algorithms
- A system for typesetting mathematics
- Derivatives of Regular Expressions
- Regular Expressions and State Graphs for Automata
- STRING-MATCHING AND OTHER PRODUCTS
- Programming Techniques: Regular expression search algorithm