Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and k-mismatch Matching

Ce Jin, Jakob Nogler

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…