  We give a sublinear quantum algorithm for the longest common substring (LCS)
problem on the run-length encoded (RLE) inputs, under the assumption that the
prefix-sums of the runs are given. Our algorithm costs $\tilde{O}(n^{5/6})\cdot
O(\mathrm{polylog}(\tilde{n}))$ time, where $n$ and $\tilde{n}$ are the encoded
and decoded length of the inputs, respectively. We justify the use of the
prefix-sum oracles by showing that, without the oracles, there is a
$\Omega(n/\log^2n)$ lower-bound on the quantum query complexity of finding LCS
given two RLE strings due to a reduction of $\mathsf{PARITY}$ to the problem.
