article Open AccessTop 10% cited

Efficient string matching

Communications of the ACM · 1975 · Vol. 18(6) · pp. 333–340

Alfred V. Aho✉(Nokia (United States))Margaret J. Corasick(Nokia (United States))

Abstract

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.

Algorithms and Data Compression semigroups and automata theory DNA and Biological ComputingString searching algorithmCommentz-Walter algorithmComputer scienceFinite-state machinePattern matchingString (physics)Matching (statistics)Approximate string matchingState (computer science)Algorithm

Citations

2,924

FWCI

16.29

field-weighted impact

References

Percentile

99%

vs. same field & year

Citations per year

Cited by

Techniques for automatically correcting words in text