  Longest common substring (LCS), longest palindrome substring (LPS), and Ulam
distance (UL) are three fundamental string problems that can be classically
solved in near linear time. In this work, we present sublinear time quantum
algorithms for these problems along with quantum lower bounds. Our results shed
light on a very surprising fact: Although the classic solutions for LCS and LPS
are almost identical (via suffix trees), their quantum computational
complexities are different. While we give an exact $\tilde O(\sqrt{n})$ time
algorithm for LPS, we prove that LCS needs at least time $\tilde
\Omega(n^{2/3})$ even for 0/1 strings.
