{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,30]],"date-time":"2026-05-30T01:17:11Z","timestamp":1780103831060,"version":"3.54.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,8,27]],"date-time":"2015-08-27T00:00:00Z","timestamp":1440633600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council (GB)","doi-asserted-by":"publisher","award":["EP\/L021005\/1"],"award-info":[{"award-number":["EP\/L021005\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,1]]},"DOI":"10.1007\/s00453-015-0060-4","type":"journal-article","created":{"date-parts":[[2015,8,26]],"date-time":"2015-08-26T16:12:44Z","timestamp":1440605564000},"page":"16-39","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":68,"title":["Quantum Pattern Matching Fast on Average"],"prefix":"10.1007","volume":"77","author":[{"given":"Ashley","family":"Montanaro","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,8,27]]},"reference":[{"key":"60_CR1","doi-asserted-by":"crossref","unstructured":"Ambainis, A.: Quantum lower bounds by quantum arguments. J. Comput. Syst. Sci. 64, 750\u2013767. quant-ph\/0002066 (2002)","DOI":"10.1006\/jcss.2002.1826"},{"key":"60_CR2","doi-asserted-by":"crossref","unstructured":"Andoni, A., Hassanieh, H., Indyk, P., Katabi, D.: Shift finding in sub-linear time. In: Proceedings of 24th ACM-SIAM Symposium on Discrete Algorithms, pp. 457\u2013465, (2013)","DOI":"10.1137\/1.9781611973105.33"},{"key":"60_CR3","doi-asserted-by":"crossref","unstructured":"Batu, T., Erg\u00fcn, F., Kilian, J., Magen, A., Raskhodnikova, S., Rubinfeld, R., Sami, R.: A sublinear algorithm for weakly approximating edit distance. In: Proceedings of 35th Annual ACM Symposium on Theory of Computing, pp. 316\u2013324, (2003)","DOI":"10.1145\/780542.780590"},{"key":"60_CR4","doi-asserted-by":"crossref","unstructured":"Bennett, C., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. SIAM J. Comput. 26(5), 1510\u20131523. quant-ph\/9701001 (1997)","DOI":"10.1137\/S0097539796300933"},{"issue":"10","key":"60_CR5","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1145\/359842.359859","volume":"20","author":"R Boyer","year":"1977","unstructured":"Boyer, R., Moore, S.: A fast string searching algorithm. Commun. ACM 20(10), 762\u2013772 (1977)","journal-title":"Commun. ACM"},{"key":"60_CR6","doi-asserted-by":"crossref","unstructured":"Brassard, G., H\u00f8yer, P., Mosca, M., Tapp, A.: Quantum Amplitude Amplification and Estimation. Quantum Computation and Quantum Information: A Millennium Volume, pp. 53\u201374. quant-ph\/0005055 (2002)","DOI":"10.1090\/conm\/305\/05215"},{"issue":"4\u20135","key":"60_CR7","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/BF01185431","volume":"12","author":"W Chang","year":"1994","unstructured":"Chang, W., Lawler, E.: Sublinear approximate string matching and biological applications. Algorithmica 12(4\u20135), 327\u2013344 (1994)","journal-title":"Algorithmica"},{"key":"60_CR8","unstructured":"Childs, A., van Dam, W.: Quantum algorithm for a generalized hidden shift problem. In: Proceedings of 18th ACM-SIAM Symposium on Discrete Algorithms, pp. 1225\u20131232. quant-ph\/0507190 (2007)"},{"key":"60_CR9","unstructured":"Childs, A., Kothari, R., Ozols, M., Roetteler, M.: Easy and hard functions for the boolean hidden shift problem. In: Proceedings of 8th Conference on the Theory of Quantum Computation, Communication, and Cryptography (TQC\u201913), pp. 50\u201379. arXiv:1304.4642 (2013)"},{"key":"60_CR10","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546853","volume-title":"Algorithms on Strings","author":"M Crochemore","year":"2007","unstructured":"Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on Strings. Cambridge University Press, Cambridge (2007)"},{"key":"60_CR11","doi-asserted-by":"crossref","unstructured":"Curtis, D., Meyer, D.: Towards quantum template matching. In: Proceedings of SPIE 5161, Quantum Communications and Quantum Imaging, pp. 134\u2013141, (2004)","DOI":"10.1117\/12.506669"},{"key":"60_CR12","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/j.ipl.2004.01.024","volume":"91","author":"M Ettinger","year":"2004","unstructured":"Ettinger, M., H\u00f8yer, P., Knill, E.: The quantum query complexity of the hidden subgroup problem is polynomial. Inf. Process. Lett. 91, 43\u201348 (2004). quant-ph\/0401083","journal-title":"Inf. Process. Lett."},{"key":"60_CR13","doi-asserted-by":"crossref","unstructured":"Friedl, K., Ivanyos, G., Magniez, F., Santha, M., Sen, P.: Hidden translation and orbit coset in quantum computing. In: Proceedings of 35th Annual ACM Symposium on Theory of Computing, pp. 1\u20139. quant-ph\/0211091 (2003)","DOI":"10.1145\/780542.780544"},{"key":"60_CR14","doi-asserted-by":"crossref","unstructured":"Gavinsky, D., Roetteler, M., Roland, J.: Quantum algorithm for the Boolean hidden shift problem. In: Proceedings of 17th International Computing & Combinatorics Conference (COCOON\u201911), pp. 158\u2013167. arXiv:1103.3017 (2011)","DOI":"10.1007\/978-3-642-22685-4_14"},{"issue":"3&4","key":"60_CR15","first-page":"221","volume":"13","author":"M Gharibi","year":"2013","unstructured":"Gharibi, M.: Reduction from non-injective hidden shift problem to injective hidden shift problem. Quantum Inf. Comput. 13(3&4), 221\u2013230 (2013). arXiv:1207.4537","journal-title":"Quantum Inf. Comput."},{"key":"60_CR16","doi-asserted-by":"crossref","first-page":"160501","DOI":"10.1103\/PhysRevLett.100.160501","volume":"100","author":"V Giovannetti","year":"2008","unstructured":"Giovannetti, V., Lloyd, S., Maccone, L.: Quantum random access memory. Phys. Rev. Lett. 100, 160501 (2008). arXiv:0708.1879","journal-title":"Phys. Rev. Lett."},{"issue":"2","key":"60_CR17","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1103\/PhysRevLett.79.325","volume":"79","author":"L Grover","year":"1997","unstructured":"Grover, L.: Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79(2), 325\u2013328 (1997). quant-ph\/9706033","journal-title":"Phys. Rev. Lett."},{"key":"60_CR18","doi-asserted-by":"crossref","unstructured":"H\u00f8yer, P., Mosca, M., de Wolf, R.: Quantum search on bounded-error inputs. In: Proceedings of 30th International Conference on Automata, Languages and Programming (ICALP\u201903), pp. 291\u2013299. quant-ph\/0304052 (2003)","DOI":"10.1007\/3-540-45061-0_25"},{"issue":"2","key":"60_CR19","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1137\/S0097539794275872","volume":"29","author":"J K\u00e4rkk\u00e4inen","year":"1999","unstructured":"K\u00e4rkk\u00e4inen, J., Ukkonen, E.: Two- and higher-dimensional pattern matching in optimal expected time. SIAM J. Comput. 29(2), 571\u2013589 (1999)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"60_CR20","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D Knuth","year":"1977","unstructured":"Knuth, D., Morris Jr, J., Pratt, V.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"key":"60_CR21","doi-asserted-by":"crossref","unstructured":"Kuperberg, G.: A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM J. Comput. 35(1), 170\u2013188 (2005). quant-ph\/0302112","DOI":"10.1137\/S0097539703436345"},{"key":"60_CR22","unstructured":"Kuperberg, G.: Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem. In: Proceedings of 8th Conference on the Theory of Quantum Computation, Communication, and Cryptography (TQC\u201913), pp. 20\u201334. arXiv:1112.3333 (2013)"},{"key":"60_CR23","unstructured":"Montanaro, A., de Wolf, R.: Quantum property testing. arXiv:1310.2035 (2013)"},{"issue":"3","key":"60_CR24","doi-asserted-by":"crossref","first-page":"938","DOI":"10.1137\/S0097539705447177","volume":"37","author":"C Moore","year":"2005","unstructured":"Moore, C., Rockmore, D., Russell, A., Schulman, L.: The power of strong fourier sampling: quantum algorithms for affine groups and hidden shifts. SIAM J. Comput. 37(3), 938\u2013958 (2005). quant-ph\/0503095","journal-title":"SIAM J. Comput."},{"issue":"1","key":"60_CR25","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/375360.375365","volume":"33","author":"G Navarro","year":"2001","unstructured":"Navarro, G.: A guided tour to approximate string matching. ACM Comput. Surv. 33(1), 31\u201388 (2001)","journal-title":"ACM Comput. Surv."},{"issue":"3","key":"60_CR26","first-page":"11:1","volume":"5","author":"M Ozols","year":"2013","unstructured":"Ozols, M., Roetteler, M., Roland, J.: Quantum rejection sampling. ACM Trans. Comput. Theory (TOCT) 5(3), 11:1\u201311:33 (2013). arXiv:1103.2774","journal-title":"ACM Trans. Comput. Theory (TOCT)"},{"key":"60_CR27","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/S1570-8667(03)00010-8","volume":"1","author":"H Ramesh","year":"2003","unstructured":"Ramesh, H., Vinay, V.: String matching in $$\\widetilde{O}(\\sqrt{n} + \\sqrt{m})$$ O ~ ( n + m ) quantum time. J. Discrete Algorithms 1, 103\u2013110 (2003). quant-ph\/0011049","journal-title":"J. Discrete Algorithms"},{"key":"60_CR28","unstructured":"Regev, O.: A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space. quant-ph\/0406151 (2004)"},{"key":"60_CR29","doi-asserted-by":"crossref","unstructured":"R\u00f6tteler, M.: Quantum algorithms to solve the hidden shift problem for quadratics and for functions of large Gowers norm. In: Proceedings of 39th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201909), LNCS vol. 5734, pp. 663\u2013674. arXiv:0911.4724 (2009)","DOI":"10.1007\/978-3-642-03816-7_56"},{"key":"60_CR30","doi-asserted-by":"crossref","unstructured":"R\u00f6tteler, M.: Quantum algorithms for highly non-linear Boolean functions. In: Proceedings of 21st ACM-SIAM Symposium on Discrete Algorithms, pp. 448\u2013457. arXiv:0811.3208 (2010)","DOI":"10.1137\/1.9781611973075.37"},{"key":"60_CR31","doi-asserted-by":"crossref","first-page":"8973","DOI":"10.1088\/0305-4470\/33\/48\/325","volume":"33","author":"J Twamley","year":"2000","unstructured":"Twamley, J.: A hidden shift quantum algorithm. J. Phys. A Math. Gen. 33, 8973 (2000)","journal-title":"J. Phys. A Math. Gen."},{"key":"60_CR32","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1137\/S009753970343141X","volume":"36","author":"W Dam van","year":"2006","unstructured":"van Dam, W., Hallgren, S., Ip, L.: Quantum algorithms for some hidden shift problems. SIAM J. Comput. 36, 763\u2013778 (2006). quant-ph\/0211140","journal-title":"SIAM J. Comput."},{"issue":"1","key":"60_CR33","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1137\/0220002","volume":"20","author":"U Vishkin","year":"1991","unstructured":"Vishkin, U.: Deterministic sampling\u2014a new technique for fast pattern matching. SIAM J. Comput. 20(1), 22\u201340 (1991)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"60_CR34","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1137\/0208029","volume":"8","author":"A Yao","year":"1979","unstructured":"Yao, A.: The complexity of pattern matching for a random string. SIAM J. Comput. 8(3), 368\u2013387 (1979)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0060-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0060-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0060-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0060-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,29]],"date-time":"2019-08-29T17:47:39Z","timestamp":1567100859000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0060-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8,27]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["60"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0060-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,8,27]]}}}