Efficient string algorithmics
Dany Breslauer · 1992
Problems involving strings arise in many areas of computer science and have numerous practical applications. We consider several problems from a theoretical perspective and provide efficient algorithms and lower bounds for these problems in sequential and parallel models of computation. In the sequential setting, we present new algorithms for the string matching problem improving the previous bounds on the number of comparisons performed by such algorithms. In parallel computation, we present tight algorithms and lower bounds for the string matching problem, for finding the periods of a string, for detecting squares and for finding initial palindromes. Contents 1 Introduction 1 1.1 Methods of Analysis : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1 1.2 Properties of Strings : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2 1.2.1 The Alphabet : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2 1.2.2 Periods : : : : : : : : : : : : : : : : : : : : :...