Near-Optimal Quantum Algorithm for Finding the Longest Common Substring between Run-Length Encoded Strings

Abstract

We give a near-optimal quantum algorithm for the longest common substring (LCS) problem between two run-length encoded (RLE) strings, with the assumption that the prefix-sums of the run-lengths are given. Our algorithm costs $\tilde{\mathcal{O}}(n^{2/3}/d^{1/6-o(1)}\cdot\mathrm{polylog}(\tilde{n}))$ time, while the query lower bound for the problem is $\tilde{\Omega}(n^{2/3}/d^{1/6})$, where $n$ and $\tilde{n}$ are the encoded and decoded length of the inputs, respectively, and $d$ is the encoded length of the LCS. We justify the use of prefix-sum oracles for two reasons. First, we note that creating the prefix-sum oracle only incurs a constant overhead in the RLE compression. Second, we show that, without the oracles, there is a $\Omega(n/\log^2n)$ lower bound on the quantum query complexity of finding the LCS given two RLE strings due to a reduction of $\mathsf{PARITY}$ to the problem. With a small modification, our algorithm also solves the longest repeated substring problem for an RLE string.