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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Quantum Algorithms for Longest Common Substring with a Gap

  • Daniel Gibney,
  • Md Helal Hossen

摘要

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.