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

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

An Improved Pattern-Matching 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 straight-line programs (or alternatively in terms of context-free grammars or recurrences). Examples of such strings are {\em Fibonacci words} and {\em Thue-Morse words}, see [4]. Usually the strings of descriptive size $n$ are of exponential length with respect to $n$. A complicated algorithm for the {\em equality-test} (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 pattern-matching} problem by using $O(n^3)$ instances of the {\em equality-test}, 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 equality-test. The latter problem is a special instance of the pattern-matching 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 bottom-up}, while the construction of [6] is quite different and works {\em top-down} in the sense of evaluation trees for straight-line programs (or derivation trees in the case of grammars).

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

Powered by Zope