Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and k -mismatch Matching
Ce Jin, Jakob Nogler · Society for Industrial and Applied Mathematics eBooks · 2023
Longest Common Substring (LCS) is an important text processing problem, which has recently been investigated in the quantum query model. The decisional version of this problem, LCS with threshold d, asks whether two length-n input strings have a common substring of length d. The two extreme cases, d = 1 and d = n, correspond respectively to Element Distinctness and Unstructured Search, two fundamental problems in quantum query complexity. However, the intermediate case 1 ≪ d ≪ n was not fully understood.