The Prague Stringology Conference 2001

Thomas Berry and S. Ravindran

A linear time string matching algorithm on average with efficient text storage

In this paper we describe an algorithm to search for a pattern in an efficiently stored text. The method used to store the text tranforms it to log2(s)/8 of its original size, where s is the size of the alphabet set. We prove that the algorithm takes linear time on average. We compare the new algorithm with some existing string matching algorithms by experimentation.

Download paper: Article in PostScript Article in PDF
 PostScript   PDF