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

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 {mathcal{O}}\(n^2/3/d^1/6-o(1\)cdotpolylog\({n}\)) time, while the query lower bound for the problem is Ω\(n^2/3/d^1/6\), where n and {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 Ω\(n/log²ⁿ\) 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.