|
A grammar-compressed (GC) string is a string
generated by a context-free grammar.
This compression model captures many practical applications,
and includes LZ78 and LZW compression as a special case.
We give an efficient algorithm for threshold approximate matching
on a GC-text against a plain pattern.
Our algorithm improves on existing algorithms
whenever the pattern is sufficiently long.
The algorithm employs the technique
of fast unit-Monge matrix distance multiplication,
as well as a new technique for implicit
unit-Monge matrix searching,
which we believe to be of independent interest.
|
