An Efficient Pattern-Matching Algorithm for Strings with Short Descriptions.
Marek Karpiński, Wojciech Rytter, Ayumi Shinohara · 1997
We investigate the time complexity of the pattern matching problem for strings which are succinctly described in terms of straight-line programs, in which the constants are symbols and the only operation is the concatenation. Most strings of descriptive size n are of exponential length with respect to n. We show an O(n 4 log n) time algorithm for this problem. The crucial point in our algorithm is the succinct representation of all periods of a (possibly long) string described in this manner. We also show a (rather straightforward) result that a very simple extension of the pattern-matching problem for shortly described strings is NP-complete.