String Matching in $\tilde{O}(\sqrt{n}+\sqrt{m})$ Quantum Time

H. Ramesh, V. Vinay

We show how to determine whether a given pattern p of length m occurs in a given text t of length n in $\tilde{O}(\sqrt{n}+\sqrt{m})$\footnote{$\tilde{O}$ allows for logarithmic…