We consider several types of internal queries, that is, questions about fragments of a given
text specified in constant space by their locations in. Our main result is an optimal data …

Longest common substring (LCS) is an important text processing problem, which has
recently been investigated in the quantum query model. The decision version of this …

Measuring sequence similarity and compressing texts are among the most fundamental
tasks in string algorithms. In this work, we develop near-optimal quantum algorithms for the …

We initiate a systematic study of the time complexity of quantum divide and conquer
algorithms for classical problems. We establish generic conditions under which search and …

The decades-old Pattern Matching with Edits problem, given a length-n string T (the text), a
length-m string P (the pattern), and a positive integer k (the threshold), asks to list all …

Abstract Approximate Pattern Matching is among the most fundamental string-processing
tasks. Given a text T of length n, a pattern P of length m, and a threshold k, the task is to …

We design near-optimal quantum query algorithms for two important text processing
problems: Longest Common Substring and Lexicographically Minimal String Rotation …