20.11.2008

A new string-matching algorithm working in constant space and linear time is presented. It is based on a powerful idea of sampling, originally introduced in parallel computations. The Algorithm uses a sample S which consists of two positions inside the pattern P. First the positions of the sample S are tested against the corresponding positions of the text T, the a version of Knuth-Morris-Pratt algorithm is applied. This gives the simplest known string-matching algorithm which works in constant space and linear time and which does not use any linear order of the alphabet. A refined version of the algorithm gives the fastest (in the sense of number of comparisons) known algorithm for string-matching in constant space. It makes (1+ε)n+O(n/m) symbol comparisons. This improves substantially the result of [3], where a (3/2+ε)n comparisons constant space algorithm was designed.