  We study quantum algorithms for several fundamental string problems,
including Longest Common Substring, Lexicographically Minimal String Rotation,
and Longest Square Substring. These problems have been widely studied in the
stringology literature since the 1970s, and are known to be solvable by
near-linear time classical algorithms. In this work, we give quantum algorithms
for these problems with near-optimal query complexities and time complexities.
Specifically, we show that:
  - Longest Common Substring can be solved by a quantum algorithm in $\tilde
O(n^{2/3})$ time, improving upon the recent $\tilde O(n^{5/6})$-time algorithm
by Le Gall and Seddighin (2020). Our algorithm uses the MNRS quantum walk
framework, together with a careful combination of string synchronizing sets
(Kempa and Kociumaka, 2019) and generalized difference covers.
  - Lexicographically Minimal String Rotation can be solved by a quantum
algorithm in $n^{1/2 + o(1)}$ time, improving upon the recent $\tilde
O(n^{3/4})$-time algorithm by Wang and Ying (2020). We design our algorithm by
first giving a new classical divide-and-conquer algorithm in near-linear time
based on exclusion rules, and then speeding it up quadratically using nested
Grover search and quantum minimum finding.
  - Longest Square Substring can be solved by a quantum algorithm in $\tilde
O(\sqrt{n})$ time. Our algorithm is an adaptation of the algorithm by Le Gall
and Seddighin (2020) for the Longest Palindromic Substring problem, but uses
additional techniques to overcome the difficulty that binary search no longer
applies.
  Our techniques naturally extend to other related string problems, such as
Longest Repeated Substring, Longest Lyndon Substring, and Minimal Suffix.

Data Structures and Algorithms;Quantum Physics