Showing quant-phShow all
2 papers · 1 filter
quant-ph2024
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…
quant-ph2023
A sublinear time quantum algorithm for longest common substring problem between run-length encoded strings
Tzu-Ching Lee, Han-Hsuan Lin
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 a…