  The divide-and-conquer framework, used extensively in classical algorithm
design, recursively breaks a problem of size $n$ into smaller subproblems (say,
$a$ copies of size $n/b$ each), along with some auxiliary work of cost
$C^{\textrm{aux}}(n)$, to give a recurrence relation $$C(n) \leq a \, C(n/b) +
C^{\textrm{aux}}(n)$$ for the classical complexity $C(n)$. We describe a
quantum divide-and-conquer framework that, in certain cases, yields an
analogous recurrence relation $$C_Q(n) \leq \sqrt{a} \, C_Q(n/b) +
O(C^{\textrm{aux}}_Q(n))$$ that characterizes the quantum query complexity. We
apply this framework to obtain near-optimal quantum query complexities for
various string problems, such as (i) recognizing regular languages; (ii)
decision versions of String Rotation and String Suffix; and natural
parameterized versions of (iii) Longest Increasing Subsequence and (iv) Longest
Common Subsequence.
