Combinatorics

String metric

Block (permutation group theory)

Mathematics

Mathematical physics

Algorithm

Statistics

Commentz-Walter algorithm

Epistemology

String (physics)

Philosophy

Artificial intelligence

Matching (statistics)

Programming language

Constant (computer programming)

Computer science

Simple (philosophy)

Efficient algorithm

Approximate string matching

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