
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 1995  Copyright 1995 Universität Bonn, Institut für Informatik, Abt. V  
85135

An Improved PatternMatching Algorithm for Strings with Short Descriptions
Marek Karpinski, Wojciech Rytter, Ayumi Shinohara [Download PostScript] [Download PDF] We improve the time complexity of the pattern matching problem for strings which are succinctly described in terms of straightline programs (or alternatively in terms of contextfree grammars or recurrences). Examples of such strings are {\em Fibonacci words} and {\em ThueMorse words}, see [4]. Usually the strings of descriptive size $n$ are of exponential length with respect to $n$. A complicated algorithm for the {\em equalitytest} (testing if two shortly described strings are the same) in $O(n^4)$ time was constructed in [6]. This algorithm was extended in [5] to the {\em patternmatching} problem by using $O(n^3)$ instances of the {\em equalitytest}, this gave $O(n^7)$ time. In this paper we reduce the time complexity to $O(n^4 \log{n})$. We show that the pattern matching for shortly described strings can be done without applying an algorithm from [6] and the problem has the similar asymptotic complexity as the best algorithm for the equalitytest. The latter problem is a special instance of the patternmatching problem and can be solved by our algorithm. The crucial point in the algorithm is the succinct (linear size) representation of all (potentially many) periods of a string of an exponential size. The structure of our algorithm is {\em bottomup}, while the construction of [6] is quite different and works {\em topdown} in the sense of evaluation trees for straightline programs (or derivation trees in the case of grammars). 

Last Change:
08/25/04 at 07:24:28
English 
Universität Bonn > Institut für Informatik > Abteilung V 