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

Simple item page
dc.creatorRamesh, H.
dc.creatorVinay, V.
dc.date2000-11-13
dc.date.accessioned2026-07-07T06:01:10Z
dc.date.available2026-07-07T06:01:10Z
dc.descriptionWe 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}.
dc.description7 pages Latex2e file
dc.identifierhttps://arxiv.org/abs/quant-ph/0011049
dc.identifierhttp://arxiv.org/abs/quant-ph/0011049
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/89174
dc.subjectQuantum Physics
dc.titleString Matching in ${\tilde O}(\sqrt{n}+\sqrt{m})$ Quantum Time
dc.typetext

Files

Collections

arXiv