Quantum Algorithms for Longest Common Substring with a Gap
摘要
Recent breakthroughs have provided a sublinear time quantum algorithm for the Longest Common Substring Problem running in \(\widetilde{\mathcal {O}}(n^{2/3}/d^{1/6})\) time for two strings of length at most n, where d is the length of the solution. At the same time, no subquadratic time quantum algorithm for the Longest Common Subsequence Problem is known, implying increasing difficulty as gaps are allowed within the solution. In this work, we consider the problem of finding two ordered matching substrings such that their total length is maximized. We present a strongly sublinear-time quantum algorithm.