Efficient randomized pattern-matching algorithms
Richard M. Karp, Michael O. Rabin · IBM Journal of Research and Development · 1987
We present randomized algorithms to solve the following string-matching problem and some of its generalizations: Given a string X of length n (the pattern) and a string Y (the text), find the first occurrence of X as a consecutive block within Y. The algorithms represent strings of length n by much shorter strings called fingerprints, and achieve their efficiency by manipulating fingerprints instead of longer strings. The algorithms require a constant number of storage locations, and essentially run in real time. They are conceptually simple and easy to implement. The method readily generalizes to higher-dimensional pattern-matching problems.
Cited by 1,269 works. doi:10.1147/rd.312.0249
Authors
References
- A Fast Monte-Carlo Test for Primality
- Fast Pattern Matching in Strings
- A fast string searching algorithm
- Approximate formulas for some functions of prime numbers
- Probabilistic algorithm for testing primality
- Rapid identification of repeated patterns in strings, trees and arrays
- Time-space-optimal string matching
- Optimal parallel pattern matching in strings
- Two dimensional pattern matching
- Saving Space in Fast String-Matching