{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T21:25:11Z","timestamp":1776288311713,"version":"3.50.1"},"reference-count":79,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T00:00:00Z","timestamp":1698105600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T00:00:00Z","timestamp":1698105600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"MEXT Quantum Leap Flagship Program","award":["JPMXS0120319794"],"award-info":[{"award-number":["JPMXS0120319794"]}]},{"name":"National Key Research and Development Program of China","award":["2018YFA0306701"],"award-info":[{"award-number":["2018YFA0306701"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61832015"],"award-info":[{"award-number":["61832015"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Lexicographically minimal string rotation (LMSR) is a problem to find the minimal one among all rotations of a string in the lexicographical order, which is widely used in equality checking of graphs, polygons, automata and chemical structures. In this paper, we propose an<jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n^{3\/4})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>O<\/mml:mi><mml:mo>(<\/mml:mo><mml:msup><mml:mi>n<\/mml:mi><mml:mrow><mml:mn>3<\/mml:mn><mml:mo>\/<\/mml:mo><mml:mn>4<\/mml:mn><\/mml:mrow><\/mml:msup><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>quantum query algorithm for LMSR. In particular, the algorithm has average-case query complexity<jats:inline-formula><jats:alternatives><jats:tex-math>$$O(\\sqrt{n} \\log n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>O<\/mml:mi><mml:mo>(<\/mml:mo><mml:msqrt><mml:mi>n<\/mml:mi><\/mml:msqrt><mml:mo>log<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, which is shown to be asymptotically optimal up to a polylogarithmic factor, compared to its<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Omega \\left( \\sqrt{n\/\\log n}\\right) $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>\u03a9<\/mml:mi><mml:mfenced><mml:msqrt><mml:mrow><mml:mi>n<\/mml:mi><mml:mo>\/<\/mml:mo><mml:mo>log<\/mml:mo><mml:mi>n<\/mml:mi><\/mml:mrow><\/mml:msqrt><\/mml:mfenced><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>lower bound. Furthermore, we show that our quantum algorithm outperforms any (classical) randomized algorithms in both worst and average cases. As an application, it is used in benzenoid identification and disjoint-cycle automata minimization.<\/jats:p>","DOI":"10.1007\/s00224-023-10146-8","type":"journal-article","created":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T09:04:33Z","timestamp":1698138273000},"page":"29-74","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Quantum Algorithm for Lexicographically Minimal String Rotation"],"prefix":"10.1007","volume":"68","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5107-8279","authenticated-orcid":false,"given":"Qisheng","family":"Wang","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4847-702X","authenticated-orcid":false,"given":"Mingsheng","family":"Ying","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,10,24]]},"reference":[{"issue":"35","key":"10146_CR1","doi-asserted-by":"publisher","first-page":"6741","DOI":"10.1088\/0305-4470\/34\/35\/302","volume":"34","author":"A Ambainis","year":"1999","unstructured":"Ambainis, A., de Wolf, R.: Average-case quantum query complexity. J. Phys. A Gen. Phys. 34(35), 6741\u20136754 (1999)","journal-title":"J. Phys. A Gen. Phys."},{"key":"10146_CR2","volume-title":"The Design and Analysis of Computer Algorithms","author":"AV Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley (1974)"},{"key":"10146_CR3","doi-asserted-by":"crossref","unstructured":"Apostolico, A., Iliopoulos, C.S., Paige, R.: An $$O(n \\log n)$$ cost parallel algorithm for the one function partitioning problem. In: Proceedings of the International Workshop on Parallel Algorithms and Architectures, pp. 70\u201376 (1987)","DOI":"10.1007\/3-540-18099-0_30"},{"key":"10146_CR4","doi-asserted-by":"crossref","unstructured":"Akmal, S., Jin, C.: Near-optimal quantum algorithms for string problems. In: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2791\u20132832 (2022)","DOI":"10.1137\/1.9781611977073.109"},{"key":"10146_CR5","unstructured":"Ahuja, A., Kapoor, S.: A quantum algorithm for finding the maximum. (1999). arXiv:quant-ph\/9911082"},{"issue":"5\u20136","key":"10146_CR6","first-page":"439","volume":"14","author":"A Ambainis","year":"2014","unstructured":"Ambainis, A., Montanaro, A.: Quantum algorithms for search with wildcards and combinatorial group testing. Quantum. Inf. Comput. 14(5\u20136), 439\u2013453 (2014)","journal-title":"Quantum. Inf. Comput."},{"key":"10146_CR7","doi-asserted-by":"crossref","unstructured":"Ambainis, A.: Quantum lower bounds by quantum arguments. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 636\u2013643 (2000)","DOI":"10.1145\/335305.335394"},{"key":"10146_CR8","doi-asserted-by":"crossref","unstructured":"Ambainis, A.: Quantum query algorithms and lower bounds. In: Classical and New Paradigms of Computation and their Complexity Hierarchies, pp. 15\u201332 (2004)","DOI":"10.1007\/978-1-4020-2776-5_2"},{"issue":"1","key":"10146_CR9","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/S0097539705447311","volume":"37","author":"A Ambainis","year":"2007","unstructured":"Ambainis, A.: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37(1), 210\u2013239 (2007)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10146_CR10","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1016\/j.ipl.2008.01.003","volume":"107","author":"J Almeida","year":"2008","unstructured":"Almeida, J., Zeitoun, M.: Description and analysis of a bottom-up DFA minimization algorithm. Inf. Process. Lett. 107(2), 52\u201359 (2008)","journal-title":"Inf. Process. Lett."},{"key":"10146_CR11","volume-title":"Algebraic approach to several families of chemical graphs","author":"N Ba\u0161i\u0107","year":"2016","unstructured":"Ba\u0161i\u0107, N.: PhD thesis, Faculty of Mathematics and Physics. In: Algebraic approach to several families of chemical graphs. University of Ljubljana (2016)"},{"issue":"5","key":"10146_CR12","doi-asserted-by":"publisher","first-page":"1524","DOI":"10.1137\/S0097539796300933","volume":"26","author":"CH Bennett","year":"1997","unstructured":"Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. SIAM J. Comput. 26(5), 1524\u20131540 (1997)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"10146_CR13","doi-asserted-by":"publisher","first-page":"778","DOI":"10.1145\/502090.502097","volume":"48","author":"R Beals","year":"2001","unstructured":"Beals, R., Buhrman, H., Cleve, R., Mosca, M., de Wolf, R.: Quantum lower bounds by polynomials. J. ACM 48(4), 778\u2013797 (2001)","journal-title":"J. ACM"},{"key":"10146_CR14","unstructured":"Berstel, J., Boasson, L., Carton, O., Fagnot, I.: Minimization of automata. (2010). arXiv:1010.5318"},{"issue":"4\u20135","key":"10146_CR15","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P","volume":"46","author":"M Boyer","year":"1998","unstructured":"Boyer, M., Brassard, G., Hoeyer, P., Tapp, A.: Tight bounds on quantum searching. Fortschr. der Physik. 46(4\u20135), 493\u2013505 (1998)","journal-title":"Fortschr. der Physik."},{"key":"10146_CR16","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Cleve, R., de\u00a0Wolf, R., Zalka, C.: Bounds for small-error and zero-error quantum algorithms. In: Proceedings of the Fortieth IEEE Annual Symposium on Foundations of Computer Science, pp. 358\u2013368 (1999)","DOI":"10.1109\/SFFCS.1999.814607"},{"issue":"1","key":"10146_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.disc.2004.11.002","volume":"280","author":"F Bassino","year":"2005","unstructured":"Bassino, F., Cl\u00e9ment, J., Nicaud, C.: The standard factorization of Lyndon words: an average point of view. Discret. Math. 280(1), 1\u201325 (2005)","journal-title":"Discret. Math."},{"key":"10146_CR18","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Cleve, R., Wigderson, A.: Quantum vs. classical communication and computation. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 63\u201368 (1998)","DOI":"10.1145\/276698.276713"},{"issue":"1","key":"10146_CR19","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0304-3975(01)00144-X","volume":"288","author":"H Buhrman","year":"2002","unstructured":"Buhrman, H., de Wolf, R.: Complexity measures and decision tree complexity: A survey. Theor. Comput. Sci. 288(1), 21\u201343 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"10146_CR20","doi-asserted-by":"crossref","unstructured":"Boroujeni, M., Ehsani, S., Ghodsi, M., HajiAghayi, M., Seddighin, S.: Approximating edit distance in truly subquadratic time: Quantum and mapreduce. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1170\u20131189 (2018)","DOI":"10.1137\/1.9781611975031.76"},{"issue":"4\u20135","key":"10146_CR21","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1016\/0020-0190(80)90149-0","volume":"10","author":"KS Booth","year":"1980","unstructured":"Booth, K.S.: Lexicographically least circular substrings. Inf. Process. Lett. 10(4\u20135), 240\u2013242 (1980)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"10146_CR22","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/j.jcss.2004.02.002","volume":"69","author":"H Barnum","year":"2004","unstructured":"Barnum, H., Saks, M.: A lower bound on the quantum query complexity of read-once functions. J. Comput. Syst. Sci. 69(2), 244\u2013258 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"10146_CR23","doi-asserted-by":"crossref","unstructured":"Buhrman, H., \u0160palek, R.: Quantum verification of matrix products. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm, pp. 880\u2013889 (2006)","DOI":"10.1145\/1109557.1109654"},{"key":"10146_CR24","doi-asserted-by":"crossref","unstructured":"Brandao, F.G.S.L., Svore, K.M.: Quantum speed-ups for solving semidefinite programs. In: Proceedings of the 58th Annual Symposium on Foundations of Computer Science, pp. 415\u2013426 (2017)","DOI":"10.1109\/FOCS.2017.45"},{"issue":"1","key":"10146_CR25","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1137\/0210015","volume":"10","author":"CJ Colbourn","year":"1980","unstructured":"Colbourn, C.J., Booth, K.S.: Linear time automorphism algorithms for trees, interval graphs, and planar graphs. SIAM J. Comput. 10(1), 203\u2013225 (1980)","journal-title":"SIAM J. Comput."},{"key":"10146_CR26","doi-asserted-by":"crossref","unstructured":"Cerf, N.J., Grover, L.K., Williams, C.P.: Nested quantum search and structured problems. Phys. Rev. A 61(3), 032303 (2000)","DOI":"10.1103\/PhysRevA.61.032303"},{"key":"10146_CR27","doi-asserted-by":"crossref","unstructured":"Cleve, R., Gavinsky, D., Yonge-Mallo, D.L.: Quantum algorithms for evaluating MIN-MAX trees. In: Theory of Quantum Computation, Communication, and Cryptography: Third Workshop, TQC 2008, pp. 11\u201315, (2008)","DOI":"10.1007\/978-3-540-89304-2_2"},{"key":"10146_CR28","doi-asserted-by":"publisher","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 (2007)"},{"key":"10146_CR29","doi-asserted-by":"crossref","unstructured":"Cleve, R., Iwama, K., Le\u00a0Gall, F., Nishimura, H., Tani, S., Teruyama, J., Yamashita, S.: Reconstructing strings from substrings with quantum queries. In Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm Theory, pp. 388\u2013397 (2012)","DOI":"10.1007\/978-3-642-31155-0_34"},{"key":"10146_CR30","unstructured":"Childs, A.M., Kothari, R., Kovacs-Deak, M., Sundaram, A., Wang, D.: Quantum divide and conquer. (2022) arXiv:2210.06419"},{"key":"10146_CR31","volume-title":"Text Algorithms","author":"M Crochemore","year":"1994","unstructured":"Crochemore, M., Rytter, W.: Text Algorithms. Oxford University Press (1994)"},{"issue":"1","key":"10146_CR32","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0304-3975(92)90134-2","volume":"92","author":"M Crochemore","year":"1992","unstructured":"Crochemore, M.: String-matching on ordered alphabets. Theor. Comput. Sci. 92(1), 33\u201347 (1992)","journal-title":"Theor. Comput. Sci."},{"key":"10146_CR33","unstructured":"D\u00fcrr, C., H\u00f8yer, P.: A quantum algorithm for finding the minimum. (1996). arXiv:quant-ph\/9607014"},{"key":"10146_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejc.2018.03.006","volume":"72","author":"PB Dragon","year":"2018","unstructured":"Dragon, P.B., Hernandez, O.I., Sawada, J., Williams, A., Wong, D.: Constructing de Bruijn sequences with co-lexicographic order: The k-ary Grandmama sequence. Eur. J. Comb. 72, 1\u201311 (2018)","journal-title":"Eur. J. Comb."},{"key":"10146_CR35","volume-title":"Handbook of Polycyclic Hydrocarbons: Part A","author":"JR Dias","year":"1987","unstructured":"Dias, J.R.: Handbook of Polycyclic Hydrocarbons: Part A. Elsevier, Benzenoid Hydrocarbons. Physical Sciences Data (1987)"},{"key":"10146_CR36","volume-title":"Handbook of Polycyclic Hydrocarbons: Part B","author":"JR Dias","year":"1988","unstructured":"Dias, J.R.: Handbook of Polycyclic Hydrocarbons: Part B. Elsevier, Polycyclic Isomers and Heteroatom Analogs of Benzenoid Hydrocarbons. Physical Sciences Data (1988)"},{"issue":"8","key":"10146_CR37","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/0196-6774(83)90017-2","volume":"8","author":"JP Duval","year":"1983","unstructured":"Duval, J.P.: Factorizing words over an ordered alphabet. J. Algoritm. 8(8), 363\u2013381 (1983)","journal-title":"J. Algoritm."},{"key":"10146_CR38","unstructured":"Gonnet, G.H., Baeza-Yates, R.A., Snider, T.: New indices for text: PAT trees and PAT arrays. In: Information Retrieval: Data Structures and Algorithms, pp. 66\u201382 (1992)"},{"key":"10146_CR39","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-eighth Annual ACM Symposium onTheory of Computing, pp. 212\u2013219, (1996)","DOI":"10.1145\/237814.237866"},{"key":"10146_CR40","doi-asserted-by":"publisher","DOI":"10.1201\/9780203490204","volume-title":"Handbook of Graph Theory","author":"JL Gross","year":"2003","unstructured":"Gross, J.L., Yellen, J.: Handbook of Graph Theory. CRC Press (2003)"},{"key":"10146_CR41","doi-asserted-by":"crossref","unstructured":"Harrow, A.W., Hassidim, A., Lloyd, S.: Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103(15), 150502 (2009)","DOI":"10.1103\/PhysRevLett.103.150502"},{"issue":"2","key":"10146_CR42","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0166-1280(95)04139-7","volume":"363","author":"P Hansen","year":"1996","unstructured":"Hansen, P., Lebatteux, C., Zheng, M.: The boundary-edges code for polyhexes. J. Mol. Struct: THEOCHEM 363(2), 237\u2013247 (1996)","journal-title":"J. Mol. Struct: THEOCHEM"},{"key":"10146_CR43","doi-asserted-by":"crossref","unstructured":"H\u00f8yer, P., Mosca, M., de\u00a0Wolf, R.: Quantum search on bounded-error inputs. In: International Colloquium on Automata, Languages, and Programming, pp. 291\u2013299 (2003)","DOI":"10.1007\/3-540-45061-0_25"},{"key":"10146_CR44","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"JE Hopcroft","year":"2000","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 2nd edn. Addison-Wesley (2000)","edition":"2"},{"issue":"301","key":"10146_CR45","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13\u201330 (1963)","journal-title":"J. Am. Stat. Assoc."},{"key":"10146_CR46","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.E.: An $$n \\log n$$ algorithm for minimizing states in a finite automaton. In: Proceedings of an International Symposium on the Theory of Machines and Computations, pp. 189\u2013196 (1971)","DOI":"10.1016\/B978-0-12-417750-5.50022-1"},{"key":"10146_CR47","doi-asserted-by":"crossref","unstructured":"Iliopoulos, C.S., Smyth, W.F.: PRAM algorithms for identifying polygon similarity. In: Proceedings of the International Symposium on Optimal Algorithms, pp. 25\u201332 (1989)","DOI":"10.1007\/3-540-51859-2_4"},{"issue":"1","key":"10146_CR48","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0304-3975(92)90137-5","volume":"92","author":"CS Iliopoulos","year":"1992","unstructured":"Iliopoulos, C.S., Smyth, W.F.: Optimal algorithms for computing the canonical form of a circular string. Theor. Comput. Sci. 92(1), 87\u2013105 (1992)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20132","key":"10146_CR49","first-page":"15","volume":"57","author":"CS Iliopoulos","year":"1994","unstructured":"Iliopoulos, C.S., Smyth, W.F.: A fast average case algorithm for Lyndon decomposition. Int. J. Comput. Math. 57(1\u20132), 15\u201331 (1994)","journal-title":"Int. J. Comput. Math."},{"key":"10146_CR50","volume-title":"Theories for algorithm calculation","author":"JT Jeuring","year":"1993","unstructured":"Jeuring, J.T.: Theories for algorithm calculation. Utrecht University (1993)"},{"key":"10146_CR51","doi-asserted-by":"crossref","unstructured":"Jeffery, S., Kothari, R., Magniez, F.: Nested quantum walks with quantum data structures. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1474\u20131485 (2013)","DOI":"10.1137\/1.9781611973105.106"},{"key":"10146_CR52","doi-asserted-by":"crossref","unstructured":"Jin, C., Nogler, J.: Quantum speed-ups for string synchronizing sets, longest common substring, and $$k$$-mismatch matching. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 5090\u20135121 (2023)","DOI":"10.1137\/1.9781611977554.ch186"},{"key":"10146_CR53","unstructured":"Kapralov, R., Khadiev, K., Mokut, J., Shen, Y., Yagafarov, M.: Fast classical and quantum algorithms for online $$k$$-server problem on trees. (2020) arXiv:2008.00270"},{"issue":"2","key":"10146_CR54","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D Knuth","year":"1977","unstructured":"Knuth, D., Morris, J.H., Pratt, V.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10146_CR55","first-page":"3","volume":"72","author":"J Kovi\u010d","year":"2014","unstructured":"Kovi\u010d, J., Pisanski, T., Balaban, A.T., Fowler, P.W.: On symmetries of benzenoid systems. MATCH Commun. Math. Comput. Chem. 72(1), 3\u201326 (2014)","journal-title":"MATCH Commun. Math. Comput. Chem."},{"issue":"6","key":"10146_CR56","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1145\/1217856.1217858","volume":"53","author":"J K\u00e4rkk\u00e4inen","year":"2006","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P., Burkhardt, S.: Linear work suffix array construction. J. ACM 53(6), 918\u20139360 (2006)","journal-title":"J. ACM"},{"key":"10146_CR57","unstructured":"Le\u00a0Gall, F., Seddighin, S.: Quantum meets fine-grained complexity: Sublinear time quantum algorithms for string problems. In: Proceedings of the 13th Innovations in Theoretical Computer Science Conference, pp. 97:1\u201397:23 (2022)"},{"issue":"5","key":"10146_CR58","first-page":"433","volume":"24","author":"M Maes","year":"1991","unstructured":"Maes, M.: Polygonal shape recognition using string-matching techniques. Pattern Match. 24(5), 433\u2013440 (1991)","journal-title":"Pattern Match."},{"issue":"2","key":"10146_CR59","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"EM McCreight","year":"1976","unstructured":"McCreight, E.M.: A space-economical suffix tree construction algorithm. J. ACM 23(2), 262\u2013272 (1976)","journal-title":"J. ACM"},{"key":"10146_CR60","unstructured":"Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches. In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 319\u2013327 (1990)"},{"key":"10146_CR61","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/s00453-015-0060-4","volume":"77","author":"A Montanaro","year":"2017","unstructured":"Montanaro, A.: Quantum pattern matching fast on average. Algorithmica 77, 16\u201339 (2017)","journal-title":"Algorithmica"},{"issue":"2","key":"10146_CR62","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/050643684","volume":"37","author":"F Magniez","year":"2007","unstructured":"Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem. SIAM J. Comput. 37(2), 413\u2013424 (2007)","journal-title":"SIAM J. Comput."},{"key":"10146_CR63","doi-asserted-by":"publisher","first-page":"12962","DOI":"10.1038\/ncomms12962","volume":"7","author":"R Papadakis","year":"2016","unstructured":"Papadakis, R., Li, H., Bergman, J., Lundstedt, A., Jorner, K., Ayub, R., Haldar, S., Jahn, B.O., Denisova, A., Zietz, B., Lindh, R., Sanyal, B., Grennberg, H., Leifer, K., Ottosson, H.: Metal-free photochemical silylations and transfer hydrogenations of benzenoid hydrocarbons and graphene. Nat Commun. 7, 12962 (2016)","journal-title":"Nat Commun."},{"key":"10146_CR64","doi-asserted-by":"crossref","unstructured":"Puppis, G.: Automata for Branching and Layered Temporal Structures: An Investigation into Regularities of Infinite Transition Systems. Springer Science & Business Media (2010)","DOI":"10.1007\/978-3-642-11881-4"},{"issue":"1","key":"10146_CR65","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0304-3975(92)90142-3","volume":"92","author":"D Revuz","year":"1992","unstructured":"Revuz, D.: Minimisation of acyclic deterministic automata in linear time. Theor. Comput. Sci. 92(1), 181\u2013189 (1992)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"10146_CR66","doi-asserted-by":"publisher","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 $$\\tilde{O}(\\sqrt{n} + \\sqrt{m})$$ quantum time. J. Discret. Algoritm. 1(1), 103\u2013110 (2003)","journal-title":"J. Discret. Algoritm."},{"issue":"1\u20133","key":"10146_CR67","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1016\/S0304-3975(02)00590-X","volume":"299","author":"W Rytter","year":"2003","unstructured":"Rytter, W.: On maximal suffixes and constant-space linear-time versions of KMP algorithm. Theor. Comput. Sci. 299(1\u20133), 763\u2013774 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"10146_CR68","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1016\/0020-0190(79)90114-5","volume":"8","author":"Y Shiloach","year":"1979","unstructured":"Shiloach, Y.: A fast equivalence-checking algorithm for circular lists. Inf. Process. Lett. 8(5), 236\u2013238 (1979)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"10146_CR69","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0196-6774(81)90013-4","volume":"2","author":"Y Shiloach","year":"1981","unstructured":"Shiloach, Y.: Fast canonization of circular strings. J. Algoritm. 2(2), 107\u2013121 (1981)","journal-title":"J. Algoritm."},{"key":"10146_CR70","doi-asserted-by":"crossref","unstructured":"Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pp. 124\u2013134 (1994)","DOI":"10.1109\/SFCS.1994.365700"},{"issue":"1","key":"10146_CR71","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/j.disc.2015.08.002","volume":"339","author":"J Sawada","year":"2016","unstructured":"Sawada, J., Williams, A., Wong, D.: A surprisingly simple de Bruijn sequence construction. Discret. Math. 339(1), 127\u2013131 (2016)","journal-title":"Discret. Math."},{"key":"10146_CR72","doi-asserted-by":"crossref","unstructured":"van Apeldoorn, J., Gily\u00e9n, A., Gribling, S., de\u00a0Wolf, R.: Quantum SDP-solvers: better upper and lower bounds. In: Proceedings of the Fifty-eighth Annual Symposium on Foundations of Computer Science, pp 403\u2013414 (2017)","DOI":"10.1109\/FOCS.2017.44"},{"key":"10146_CR73","doi-asserted-by":"crossref","unstructured":"Vishkin, U.: Deterministic sampling - a new technique for fast pattern matching. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, pp. 170\u2013180 (1990)","DOI":"10.1145\/100216.100235"},{"key":"10146_CR74","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511987045","volume-title":"A Course in Combinatorics","author":"JH van Lint","year":"2001","unstructured":"van Lint, J.H., Wilson, R.W., Wilson, R.M.: A Course in Combinatorics. Cambridge University Press (2001)"},{"key":"10146_CR75","unstructured":"Wang, Q.: A note on quantum divide and conquer for minimal string rotation. (2022). arXiv:2210.09149"},{"key":"10146_CR76","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: Proceedings of the Fourteenth Annual Symposium on Switching and Automata Theory, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"},{"issue":"1","key":"10146_CR77","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1021\/nl072548a","volume":"8","author":"WL Wang","year":"2008","unstructured":"Wang, W.L., Meng, S., Kaxiras, E.: Graphene NanoFlakes with large spin. Nano Lett. 8(1), 241\u2013245 (2008)","journal-title":"Nano Lett."},{"key":"10146_CR78","doi-asserted-by":"crossref","unstructured":"Wassmann, T., Seitsonen, A.P., Saitta, A.M., Lazzeri, M., Mauri, F.: Structure, stability, edge states, and aromaticity of graphene ribbons. Phys. Rev. Lett. 101(9), 096402 (2008)","DOI":"10.1103\/PhysRevLett.101.096402"},{"issue":"4","key":"10146_CR79","doi-asserted-by":"publisher","first-page":"2746","DOI":"10.1103\/PhysRevA.60.2746","volume":"60","author":"C Zalka","year":"1999","unstructured":"Zalka, C.: Grover\u2019s quantum searching algorithm is optimal. Phys. Rev. A 60(4), 2746\u20132751 (1999)","journal-title":"Phys. Rev. A"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10146-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-023-10146-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10146-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,31]],"date-time":"2024-10-31T18:11:00Z","timestamp":1730398260000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-023-10146-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,24]]},"references-count":79,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["10146"],"URL":"https:\/\/doi.org\/10.1007\/s00224-023-10146-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,24]]},"assertion":[{"value":"24 August 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 October 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interest"}}]}}