An Improved Pattern-Matching Algorithm for Strings with Short Descriptions
Marek Karpiński, Wojciech Rytter, Ayumi Shinohara · 1995
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 \cite{Lo}. 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 \cite{Pl}. This algorithm was extended in \cite{KRS} 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 \cite{Pl} and the problem has the similar asymptotic complexity as the best algorithm for the equality-test.