Constant-space string-matching in sublinear average time

Given two strings: pattern P of length m and text T of length n. The string -matching problem is to find all occurrences of the pattern P in the text T . We present a string-matching algorithms which works in o(n) average time and constant additional space for one-dimensional texts and two-dimensional arrays. This is a first attempt to the small-space string-matching problem in which sublinear time algorithms are achieved. We show that all occurren ces of one- or two-dimensional patterns can be found in O(n/r) average time with constant memory, where r is the repetition size of P (size of the lon gest repeated subword of P). (C) 1999 Elsevier Science B.V. All rights rese rved.