Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1994 Copyright 1994 Universität Bonn, Institut für Informatik, Abt. V
85126

20.11.2008

Constant-space string matching with smaller number of comparisons: sequential sampling
Leszek Gasieniec, Wojciech Plandowski, Wojciech Rytter
[Download PostScript] [Download PDF]

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.

Last Change: 11/20/08 at 12:12:13
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope