dorsal/arxiv
View SchemaString Matching in ${\tilde O}(\sqrt{n}+\sqrt{m})$ Quantum Time
| Authors | H. Ramesh, V. Vinay |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0011049 |
| URL | https://arxiv.org/abs/quant-ph/0011049 |
Abstract
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}.
{
"annotation_id": "ba5c1aa8-fc0c-4057-b8f6-435df63d5a5e",
"date_created": "2026-03-02T18:01:42.527000Z",
"date_modified": "2026-03-02T18:01:42.527000Z",
"file_hash": "803d9f0b453731c5eb6a024459ee395de8d836aab864523c10673005ec20885b",
"private": false,
"record": {
"abstract": "We show how to determine whether a given pattern p of length m occurs in a\ngiven text t of length n in ${\\tilde O}(\\sqrt{n}+\\sqrt{m})$\\footnote{${\\tilde\nO}$ allows for logarithmic factors in m and $n/m$} time, with inverse\npolynomial failure probability. This algorithm combines quantum searching\nalgorithms with a technique from parallel string matching, called {\\em\nDeterministic Sampling}.",
"arxiv_id": "quant-ph/0011049",
"authors": [
"H. Ramesh",
"V. Vinay"
],
"categories": [
"quant-ph"
],
"title": "String Matching in ${\\tilde O}(\\sqrt{n}+\\sqrt{m})$ Quantum Time",
"url": "https://arxiv.org/abs/quant-ph/0011049"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "79b7a854-9c19-4c1a-8acc-e98aaa6967b4",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}