{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T10:09:43Z","timestamp":1776247783607,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T00:00:00Z","timestamp":1776211200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"},{"start":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T00:00:00Z","timestamp":1776211200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62002394"],"award-info":[{"award-number":["62002394"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Shenzhen Science and Technology Program","award":["202206193000001, 20220817175048002"],"award-info":[{"award-number":["202206193000001, 20220817175048002"]}]},{"DOI":"10.13039\/501100007162","name":"Department of Science and Technology of Guangdong Province","doi-asserted-by":"crossref","award":["2021QN02X239"],"award-info":[{"award-number":["2021QN02X239"]}],"id":[{"id":"10.13039\/501100007162","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2026,6]]},"DOI":"10.1007\/s00236-026-00530-5","type":"journal-article","created":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T09:15:25Z","timestamp":1776244525000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Simple linear time algorithm for sorting strings in omega-order with applications"],"prefix":"10.1007","volume":"63","author":[{"given":"Ruixi","family":"Luo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Taikun","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kai","family":"Jin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,4,15]]},"reference":[{"key":"530_CR1","unstructured":"Bentley, J.L., Sedgewick, R.: Fast algorithms for sorting and searching strings. In: Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 360\u2013369 (1997)"},{"issue":"2","key":"530_CR2","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth, D.E., Pratt, J.H.M.: Fast pattern matching in strings. SIAM Journal on Computing 6(2), 323\u2013350 (1977). https:\/\/doi.org\/10.1137\/0206024","journal-title":"SIAM Journal on Computing"},{"key":"530_CR3","unstructured":"Lothaire, M.: Combinatorics on Words. Encyclopedia of Mathematics, Vol. 17. Addison-Wesley, MA (1983)"},{"key":"530_CR4","doi-asserted-by":"publisher","first-page":"114965","DOI":"10.1109\/ACCESS.2021.3105607","volume":"9","author":"D Zhang","year":"2021","unstructured":"Zhang, D., Jin, K.: Fast algorithms for computing the statistics of pattern matching. IEEE Access 9, 114965\u2013114976 (2021). https:\/\/doi.org\/10.1109\/ACCESS.2021.3105607","journal-title":"IEEE Access"},{"issue":"5","key":"530_CR5","doi-asserted-by":"publisher","first-page":"1501","DOI":"10.1137\/15M1011032","volume":"46","author":"H Bannai","year":"2017","unstructured":"Bannai, H., I, T., Inenaga, S., Nakashima, Y., Takeda, M., Tsuruta, K.: The \u201cruns\u201d theorem. SIAM Journal on Computing 46(5), 1501\u20131514 (2017). https:\/\/doi.org\/10.1137\/15M1011032","journal-title":"SIAM Journal on Computing"},{"key":"530_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2018.08.011","volume":"806","author":"M Crochemore","year":"2020","unstructured":"Crochemore, M., Russo, L.M.S.: Cartesian and lyndon trees. Theoret. Comput. Sci. 806, 1\u20139 (2020). https:\/\/doi.org\/10.1016\/j.tcs.2018.08.011","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"530_CR7","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/0196-6774(83)90017-2","volume":"4","author":"JP Duval","year":"1983","unstructured":"Duval, J.P.: Factorizing words over an ordered alphabet. J. Algorithms 4(4), 363\u2013381 (1983). https:\/\/doi.org\/10.1016\/0196-6774(83)90017-2","journal-title":"J. Algorithms"},{"key":"530_CR8","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0304-3975(95)00098-4","volume":"161","author":"H Petersen","year":"1996","unstructured":"Petersen, H.: On the language of primitive words. Theoret. Comput. Sci. 161, 141\u2013156 (1996)","journal-title":"Theoret. Comput. Sci."},{"key":"530_CR9","unstructured":"D\u00f6m\u00f6si, P., Horv\u00e1th, S., Ito, M.: On the connection between formal languages and primitive words. In: Proc. First Session on Scientific Communication, Univ. of Oradea, Oradea, Romania, pp. 59\u201367 (1991)"},{"key":"530_CR10","unstructured":"D\u00f6m\u00f6si, P., Ito, M.: Context-Free Languages And Primitive Words, (2014). https:\/\/api.semanticscholar.org\/CorpusID:118541294"},{"issue":"1","key":"530_CR11","first-page":"5","volume":"3","author":"G Lischke","year":"2011","unstructured":"Lischke, G.: Primitive words and roots of words. Acta Univ. Sapientiae, Informatica 3(1), 5\u201334 (2011)","journal-title":"Acta Univ. Sapientiae, Informatica"},{"key":"530_CR12","unstructured":"Berstel, J., Boasson, L.: The set of Lyndon words is not context-free. Bull. EATCS 63 (1997)"},{"key":"530_CR13","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0012-365X(78)90002-X","volume":"23","author":"H Fredricksen","year":"1979","unstructured":"Fredricksen, H., Maiorana, J.: Necklaces of beads in $$k$$ colors and $$k$$-ary de Bruijn sequences. Discrete Math. 23, 207\u2013210 (1979)","journal-title":"Discrete Math."},{"issue":"12","key":"530_CR14","doi-asserted-by":"publisher","first-page":"2320","DOI":"10.1016\/j.disc.2015.05.025","volume":"338","author":"YH Au","year":"2015","unstructured":"Au, Y.H.: Generalized de Bruijn words for primitive words and powers. Discret. Math. 338(12), 2320\u20132331 (2015). https:\/\/doi.org\/10.1016\/j.disc.2015.05.025","journal-title":"Discret. Math."},{"key":"530_CR15","unstructured":"Dolce, F., Restivo, A., Reutenauer, C.: Some variations on Lyndon words. arXiv:1904.00954 (2019)"},{"issue":"3","key":"530_CR16","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1016\/j.tcs.2007.07.014","volume":"387","author":"S Mantaci","year":"2007","unstructured":"Mantaci, S., Restivo, A., Rosone, G., Sciortino, M.: An extension of the burrows-wheeler transform. Theoret. Comput. Sci. 387(3), 298\u2013312 (2007)","journal-title":"Theoret. Comput. Sci."},{"key":"530_CR17","doi-asserted-by":"crossref","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P.: Simple linear work suffix array construction. In: Automata, Languages and Programming: 30th International Colloquium, ICALP 2003 Eindhoven, The Netherlands, June 30\u2013July 4, 2003 Proceedings 30, pp. 943\u2013955 (2003). Springer","DOI":"10.1007\/3-540-45061-0_73"},{"key":"530_CR18","doi-asserted-by":"crossref","unstructured":"Hon, W.K., Ku, T.H., Lu, C.H., Shah, R., Thankachan, S.V.: Efficient algorithm for circular Burrows-Wheeler transform. In: Annual Symposium on Combinatorial Pattern Matching, pp. 257\u2013268 (2012). Springer","DOI":"10.1007\/978-3-642-31265-6_21"},{"issue":"10","key":"530_CR19","doi-asserted-by":"publisher","first-page":"1471","DOI":"10.1109\/TC.2010.188","volume":"60","author":"G Nong","year":"2010","unstructured":"Nong, G., Zhang, S., Chan, W.H.: Two efficient algorithms for linear time suffix array construction. IEEE Trans. Comput. 60(10), 1471\u20131484 (2010)","journal-title":"IEEE Trans. Comput."},{"key":"530_CR20","doi-asserted-by":"crossref","unstructured":"Boucher, C., Cenzato, D., Lipt\u00e1k, Z., Rossi, M., Sciortino, M.: Computing the original eBWT faster, simpler, and with less memory. In: International Symposium on String Processing and Information Retrieval, pp. 129\u2013142 (2021). Springer","DOI":"10.1007\/978-3-030-86692-1_11"},{"key":"530_CR21","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2024.105153","volume":"297","author":"H Bannai","year":"2024","unstructured":"Bannai, H., K\u00e4rkk\u00e4inen, J., K\u00f6ppl, D., Piatkowski, M.: Constructing and indexing the bijective and extended Burrows-Wheeler transform. Inf. Comput. 297, 105153 (2024)","journal-title":"Inf. Comput."},{"issue":"4","key":"530_CR22","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1307\/mmj\/1028998766","volume":"9","author":"RC Lyndon","year":"1962","unstructured":"Lyndon, R.C., Sch\u00fctzenberger, M.P.: The equation $$a^m=b^nc^p$$ in a free group. Michigan Math. J. 9(4), 289\u2013298 (1962). https:\/\/doi.org\/10.1307\/mmj\/1028998766","journal-title":"Michigan Math. J."},{"key":"530_CR23","doi-asserted-by":"crossref","unstructured":"Dolce, F., Restivo, A., Reutenauer, C.: On generalized Lyndon words. arXiv: 1812.04515 (2019b)","DOI":"10.1016\/j.tcs.2018.12.015"},{"key":"530_CR24","volume-title":"The Design and Analysis of Computer Algorithms","author":"AV Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E.: The Design and Analysis of Computer Algorithms, 1st edn. Addison-Wesley Longman Publishing Co., Inc, USA (1974)","edition":"1"},{"issue":"6","key":"530_CR25","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1137\/0216062","volume":"16","author":"R Paige","year":"1987","unstructured":"Paige, R., Tarjan, R.E.: Three partition refinement algorithms. SIAM J. Comput. 16(6), 973\u2013989 (1987). https:\/\/doi.org\/10.1137\/0216062","journal-title":"SIAM J. Comput."},{"key":"530_CR26","doi-asserted-by":"publisher","unstructured":"Fagerberg, R.: String sorting. In: Kao, M.Y. (ed.) Encyclopedia of Algorithms, pp. 907\u2013910. Springer, Boston, MA (2008). https:\/\/doi.org\/10.1007\/978-0-387-30162-4_408","DOI":"10.1007\/978-0-387-30162-4_408"},{"issue":"4\u20135","key":"530_CR27","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":"1","key":"530_CR28","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/s00224-023-10146-8","volume":"68","author":"Q Wang","year":"2024","unstructured":"Wang, Q., Ying, M.: Quantum algorithm for lexicographically minimal string rotation. Theo. Comput. Syst. 68(1), 29\u201374 (2024)","journal-title":"Theo. Comput. Syst."},{"issue":"2","key":"530_CR29","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. Algorithms 2(2), 107\u2013121 (1981). https:\/\/doi.org\/10.1016\/0196-6774(81)90013-4","journal-title":"J. Algorithms"},{"key":"530_CR30","doi-asserted-by":"crossref","unstructured":"Fischer, J., Heun, V.: Theoretical and practical improvements on the rmq-problem, with applications to lca and lce. In: Lewenstein, M., Valiente, G. (eds.) Combinatorial Pattern Matching, pp. 36\u201348. Springer, Berlin, Heidelberg (2006)","DOI":"10.1007\/11780441_5"},{"issue":"1","key":"530_CR31","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-018-2262-7","volume":"19","author":"P Somervuo","year":"2018","unstructured":"Somervuo, P., Koskinen, P., Mei, P., Holm, L., Auvinen, P., Paulin, L.: Barcosel: a tool for selecting an optimal barcode set for high-throughput sequencing. BMC Bioinformatics 19(1), 257 (2018)","journal-title":"BMC Bioinformatics"},{"issue":"2","key":"530_CR32","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1534\/genetics.115.176909","volume":"201","author":"JT Kang","year":"2015","unstructured":"Kang, J.T., Zhang, P., Z\u00f6llner, S., Rosenberg, N.A.: Choosing subsamples for sequencing studies by minimizing the average distance to the closest leaf. Genetics 201(2), 499\u2013511 (2015)","journal-title":"Genetics"},{"issue":"27","key":"530_CR33","doi-asserted-by":"publisher","first-page":"6217","DOI":"10.1073\/pnas.1802640115","volume":"115","author":"JA Hawkins","year":"2018","unstructured":"Hawkins, J.A., Jones, S.K., Jr., Finkelstein, I.J., Press, W.H.: Indel-correcting DNA barcodes for high-throughput sequencing. Proceedings of the National Academy of Sciences 115(27), 6217\u20136226 (2018)","journal-title":"Proceedings of the National Academy of Sciences"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-026-00530-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-026-00530-5","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-026-00530-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T09:15:35Z","timestamp":1776244535000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-026-00530-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,15]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["530"],"URL":"https:\/\/doi.org\/10.1007\/s00236-026-00530-5","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,15]]},"assertion":[{"value":"14 January 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 March 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 April 2026","order":3,"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 no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"17"}}