Efficient randomized pattern-matching algorithms

IBM Journal of Research and DevelopmentPublished 1 March 1987

Richard M. Karp, Michael O. Rabin

DOI10.1147/rd.312.0249

Citations1,277

Abstract

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.

Keywords

Computer Science

SIAM Journal on ComputingFast Pattern Matching in Strings

2,917 Citations1977Donald E. Knuth, James H. Morris +1 more

An algorithm is presented which finds all occurrences of one given string within another, in running time proportional to the sum of the lengths of the strings, showing that the set of concatenations of even palindromes, i.e., the language $\{\alpha \alpha ^R\}^*$, can be recognized in linear time.

Communications of the ACMA fast string searching algorithm

2,292 Citations1977Robert S. Boyer, J Strother Moore

The algorithm has the unusual property that, in most cases, not all of the first i.” in another string, are inspected.

View PDF

Journal of Number TheoryProbabilistic algorithm for testing primality

867 Citations1980Michael O. Rabin

The algorithm has the feature that when it determines a number composite then the result is always true, but when it asserts that a number is prime there is a provably small probability of error.

SIAM Journal on ComputingA Fast Monte-Carlo Test for Primality

643 Citations1977R. M. Solovay, Volker Strassen

A uniform distribution a from a uniform distribution on the set 1, 2, 3, 4, 5 is a random number and if a and n are relatively prime, compute the residue varepsilon.

Rapid identification of repeated patterns in strings, trees and arrays

276 Citations1972Richard M. Karp, Raymond E. Miller +1 more

This paper describes a strategy for constructing efficient algorithms for solving two types of matching problems and develops explicit algorithms for these two problems applied to strings and arrays.

Information Processing LettersTwo dimensional pattern matching

152 Citations1977Richard Bird

The purpose is to give an algorithm for thz! two dimensional case, one which follows the general approach of the K MP, and indeed uses the KMP as a subprogram, which has a running time of 0(n2 + m’), which is clearly optimal since both the pattern and the text have to be read and this takes O(rt’ + m2).

Lecture notes in computer scienceOptimal parallel pattern matching in strings

103 Citations1985Uzi Vishkin

Given a text of length n and a pattern, this work presents a parallel linear algorithm for finding all occurrences of the pattern in the text in O(n/p) time using any number of p ≤ n/log n processors on a concurrent-read concurrent-write parallel random-access-machine.

SIAM Journal on ComputingSaving Space in Fast String-Matching

31 Citations1980Zvi Galil, Joel Seiferas

Algorithms described in this paper reduce the extra space used by the Knuth–Morris–Pratt algorithm down to $O(\log |x|)$, and the time for the naive algorithm downto $O(|x|^\varepsilon |y|)$ for any fixed $\varePSilon > 0$.

Time-space-optimal string matching (Preliminary Report)

16 Citations1981Zvi Galil, Joel Seiferas

A new linear-time string-matching algorithm requiring neither dynamic storage allocation nor other high-level capabilities is described, which can be implemented to run in linear time even on a six-head two-way finite automaton.

Journal of Computer and System SciencesTime-space-optimal string matching

8 Citations1983Zvi Galil, Joel Seiferas

An algorithm is designed and analyzed which realizes both asymptotic bounds simultaneously and makes possible a completely general implementation as a Fortran subroutine or even as a six-head finite automaton.