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

Tzu-Ching Lee, Han-Hsuan Lin

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