  The convolution between a text string $S$ of length $N$ and a pattern string
$P$ of length $m$ can be computed in $O(N \log m)$ time by FFT. It is known
that various types of approximate string matching problems are reducible to
convolution. In this paper, we assume that the input text string is given in a
compressed form, as a \emph{straight-line program (SLP)}, which is a context
free grammar in the Chomsky normal form that derives a single string. Given an
SLP $\mathcal{S}$ of size $n$ describing a text $S$ of length $N$, and an
uncompressed pattern $P$ of length $m$, we present a simple $O(nm \log m)$-time
algorithm to compute the convolution between $S$ and $P$. We then show that
this can be improved to $O(\min\{nm, N-\alpha\} \log m)$ time, where $\alpha
\geq 0$ is a value that represents the amount of redundancy that the SLP
captures with respect to the length-$m$ substrings. The key of the improvement
is our new algorithm that computes the convolution between a trie of size $r$
and a pattern string $P$ of length $m$ in $O(r \log m)$ time.
