Physics – Quantum Physics
Scientific paper
2000-11-13
Physics
Quantum Physics
7 pages Latex2e file
Scientific paper
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 factors in m and $n/m$} time, with inverse polynomial failure probability. This algorithm combines quantum searching algorithms with a technique from parallel string matching, called {\em Deterministic Sampling}.
Ramesh H.
Vinay V.
No associations
LandOfFree
String Matching in ${\tilde O}(\sqrt{n}+\sqrt{m})$ Quantum Time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with String Matching in ${\tilde O}(\sqrt{n}+\sqrt{m})$ Quantum Time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and String Matching in ${\tilde O}(\sqrt{n}+\sqrt{m})$ Quantum Time will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-381097