Compressed Subsequence Matching and Packed Tree Coloring

We present a new algorithm for subsequence matching in grammar compressed strings. Given a grammar of size n compressing a string of size N and a pattern string of size m over an alphabet of size $$\sigma $$ź, our algorithm uses $$O(n+\frac{n\sigma }{w})$$O(n+nźw) space and $$O(n+\frac{n\sigma }{w}+m\log N\log w\cdot occ)$$O(n+nźw+mlogNlogw·occ) or $$O(n+\frac{n\sigma }{w}\log w+m\log N\cdot occ)$$O(n+nźwlogw+mlogN·occ) time. Here w is the word size and occ is the number of minimal occurrences of the pattern. Our algorithm uses less space than previous algorithms and is also faster for $$occ=o(\frac{n}{\log N})$$occ=o(nlogN) occurrences. The algorithm uses a new data structure that allows us to efficiently find the next occurrence of a given character after a given position in a compressed string. This data structure in turn is based on a new data structure for the tree color problem, where the node colors are packed in bit strings.