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).