Computing convolution on grammar-compressed text

Toshiya Tanaka, Tomohiro I, Shunsuke Inenaga +2

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 appro…