Statistics

Epistemology

Algorithm

Combinatorics

Commentz-Walter algorithm

Philosophy

Artificial intelligence

String (physics)

Matching (statistics)

Programming language

String metric

Constant (computer programming)

Block (permutation group theory)

Simple (philosophy)

Efficient algorithm

Approximate string matching

Mathematics

Mathematical physics

Computer science

Pattern matching

String searching algorithm

IBM Journal of Research and Development

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.

Efficient randomized pattern-matching algorithms