
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 1994  Copyright 1994 Universität Bonn, Institut für Informatik, Abt. V  
85126 20.11.2008 
Constantspace string matching with smaller number of comparisons: sequential sampling
Leszek Gasieniec, Wojciech Plandowski, Wojciech Rytter [Download PostScript] [Download PDF] A new stringmatching 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 KnuthMorrisPratt algorithm is applied. This gives the simplest known stringmatching 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 stringmatching 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 