{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,29]],"date-time":"2026-10-29T20:18:55Z","timestamp":1793305135230,"version":"4.5.0"},"reference-count":115,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2022\/46\/E\/ST6\/004"],"award-info":[{"award-number":["2022\/46\/E\/ST6\/004"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2024,10,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We consider several types of internal queries, that is, questions about fragments of a given text [Formula: see text] specified in constant space by their locations in [Formula: see text]. Our main result is an optimal data structure for internal pattern matching (IPM) queries, which, given two fragments [Formula: see text] and [Formula: see text], ask for a representation of all fragments contained in [Formula: see text] and matching [Formula: see text] exactly. This problem can be viewed as an internal version of the fundamental exact pattern matching problem: We are looking for exact occurrences of one substring of [Formula: see text] within another substring of [Formula: see text]. Our data structure answers IPM queries in time proportional to the quotient [Formula: see text] of the fragments\u2019 lengths, which is required due to the worst-case information content of the output. If [Formula: see text] is a text of length [Formula: see text] over an integer alphabet of size [Formula: see text], then our data structure occupies [Formula: see text] machine words (that is, [Formula: see text] bits) and admits an [Formula: see text]-time construction algorithm. We also show how to use IPM queries for answering internal queries corresponding to other classic string processing problems. Among others, we derive optimal data structures reporting the periods of a fragment and testing the cyclic equivalence of two fragments. Since the publication of the conference version of this paper [Kociumaka et al., Internal pattern matching queries in a text and applications, SODA 2015], IPM queries have found numerous further applications, following the path paved by the classic longest common extension (LCE) queries of Landau and Vishkin [ J.\u00a0Comput.\u00a0System Sci., 37 (1988), pp.\u00a063\u201378]. In particular, IPM queries have been implemented in grammar-compressed and dynamic settings and, along with LCE queries, constitute elementary operations of the [Formula: see text] model, developed by Charalampopoulos, Kociumaka, and Wellnitz [ Faster approximate pattern matching: A unified approach, FOCS 2020] to design approximate pattern matching algorithms that work in multiple settings. All our algorithms are deterministic, whereas the data structure in the conference version of the paper only admits a randomized construction in [Formula: see text] expected time. To achieve this, we provide a novel construction of string synchronizing sets of Kempa and Kociumaka [ String synchronizing sets: Sublinear-time BWT construction and optimal LCE data structure, STOC 2019]. Our method, based on a new restricted version of the recompression technique of Je\u017c [ J.\u00a0ACM, 63 (2016), pp.\u00a04:1\u20134:51], yields a hierarchy of [Formula: see text] string synchronizing sets covering the whole spectrum of the fragments\u2019 lengths.<\/jats:p>","DOI":"10.1137\/23m1567618","type":"journal-article","created":{"date-parts":[[2024,10,14]],"date-time":"2024-10-14T04:01:26Z","timestamp":1728878486000},"page":"1524-1577","source":"Crossref","is-referenced-by-count":12,"title":["Internal Pattern Matching Queries in a Text and Applications"],"prefix":"10.1137","volume":"53","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2477-1702","authenticated-orcid":true,"given":"Tomasz","family":"Kociumaka","sequence":"first","affiliation":[{"name":"Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbr\u00fccken, Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0067-6401","authenticated-orcid":true,"given":"Jakub","family":"Radoszewski","sequence":"additional","affiliation":[{"name":"University of Warsaw and Samsung R&D Warsaw, Warsaw, Poland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9162-6724","authenticated-orcid":true,"given":"Wojciech","family":"Rytter","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7369-3309","authenticated-orcid":true,"given":"Tomasz","family":"Wale\u0144","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,10,14]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.04.009"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.3390\/a13110276"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360855"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-022-01092-x"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4020-2776-5_2"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.10.026"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2014.02.010"},{"key":"ref8","unstructured":"A. Amir, I. Boneh, P. Charalampopoulos, and E. Kondratovsky, Repetition detection in a dynamic string, in 27th Annual European Symposium on Algorithms, ESA 2019, LIPIcs 144, Schloss Dagstuhl\u2013Leibniz Center for Informatics, Wadern, Germany, 2019, pp. 5:1\u20135:18, https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.5."},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-022-00926-y"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00744-0"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1145\/1240233.1240242"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.07.006"},{"key":"ref13","doi-asserted-by":"crossref","unstructured":"A. Amir, M. Lewenstein, and S. V. Thankachan, Range LCP queries revisited, in 22nd International Symposium on String Processing and Information Retrieval, SPIRE 2015, LNCS 9309, Springer-Verlag, Berlin, 2015, pp. 350\u2013361, https:\/\/doi.org\/10.1007\/978-3-319-23826-5_33.","DOI":"10.1007\/978-3-319-23826-5_33"},{"key":"ref14","doi-asserted-by":"crossref","unstructured":"M. Babenko, P. Gawrychowski, T. Kociumaka, and T. Starikovskaya, Wavelet trees meet suffix trees, in 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, SIAM, Philadelphia, 2015, pp. 572\u2013591, https:\/\/doi.org\/10.1137\/1.9781611973730.39.","DOI":"10.1137\/1.9781611973730.39"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2022.04.029"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1137\/15M1011032"},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"D. Belazzougui and S. J. Puglisi, Range predecessor and Lempel-Ziv parsing, in 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, SIAM, Philadelphia, 2016, pp. 2053\u20132071, https:\/\/doi.org\/10.1137\/1.9781611974331.ch143.","DOI":"10.1137\/1.9781611974331.ch143"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.06.013"},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"O. Birenzwige, S. Golan, and E. Porat, Locally consistent parsing for text indexing in small space, in 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, SIAM, Philadelphia, 2020, pp. 607\u2013626, https:\/\/doi.org\/10.1137\/1.9781611975994.37.","DOI":"10.1137\/1.9781611975994.37"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1145\/359842.359859"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294132"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00144-X"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.compedu.2008.12.001"},{"key":"ref24","doi-asserted-by":"crossref","unstructured":"T. M. Chan, S. Golan, T. Kociumaka, T. Kopelowitz, and E. Porat, Approximating text-to-pattern Hamming distances, in 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, ACM, New York, 2020, pp. 643\u2013656, https:\/\/doi.org\/10.1145\/3357713.3384266.","DOI":"10.1145\/3357713.3384266"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-021-00821-y"},{"key":"ref26","unstructured":"P. Charalampopoulos, T. Kociumaka, S. P. Pissis, and J. Radoszewski, Faster algorithms for longest common substring, in 29th Annual European Symposium on Algorithms, ESA 2021, LIPIcs 204, Schloss Dagstuhl\u2013Leibniz Center for Informatics, Wadern, Germany, 2021, pp. 30:1\u201330:17, https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2021.30."},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2020.07.003"},{"key":"ref28","unstructured":"P. Charalampopoulos, T. Kociumaka, J. Radoszewski, S. P. Pissis, W. Rytter, T. Wale\u0144, and W. Zuba, Approximate circular pattern matching, in 30th Annual European Symposium on Algorithms, ESA 2022, LIPIcs 244, Schloss Dagstuhl\u2013Leibniz Center for Informatics, Wadern, Germany, 2022, pp. 35:1\u201335:19, https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2022.35."},{"key":"ref29","doi-asserted-by":"crossref","unstructured":"P. Charalampopoulos, T. Kociumaka, J. Radoszewski, W. Rytter, T. Wale\u0144, and W. Zuba, Efficient enumeration of distinct factors using package representations, in 27th International Symposium on String Processing and Information Retrieval, SPIRE 2020, LNCS 12303, Springer-Verlag, Berlin, 2020, pp. 247\u2013261, https:\/\/doi.org\/10.1007\/978-3-030-59212-7_18.","DOI":"10.1007\/978-3-030-59212-7_18"},{"key":"ref30","doi-asserted-by":"crossref","unstructured":"P. Charalampopoulos, T. Kociumaka, and P. Wellnitz, Faster approximate pattern matching: A unified approach, in 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, IEEE, New York, 2020, pp. 978\u2013989, https:\/\/doi.org\/10.1109\/FOCS46700.2020.00095.","DOI":"10.1109\/FOCS46700.2020.00095"},{"key":"ref31","doi-asserted-by":"crossref","unstructured":"P. Charalampopoulos, T. Kociumaka, and P. Wellnitz, Faster pattern matching under edit distance: A reduction to dynamic puzzle matching and the seaweed monoid of permutation matrices, in 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, IEEE, New York, 2022, pp. 698\u2013707, https:\/\/doi.org\/10.1109\/FOCS54457.2022.00072.","DOI":"10.1109\/FOCS54457.2022.00072"},{"key":"ref32","unstructured":"P. Charalampopoulos, S. P. Pissis, J. Radoszewski, W. Rytter, T. Wale\u0144, and W. Zuba, Approximate circular pattern matching under edit distance, in 41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024, LIPIcs 289, Schloss Dagstuhl\u2013Leibniz Center for Informatics, Wadern, Germany, 2024, pp. 24:1\u201324:22, https:\/\/doi.org\/10.4230\/LIPICS.STACS.2024.24."},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.2307\/1970044"},{"key":"ref34","unstructured":"G. Cormode and S. Muthukrishnan, Substring compression problems, in 16th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, SIAM, Philadelphia, 2005, pp. 321\u2013330, http:\/\/dl.acm.org\/citation.cfm?id=1070432.1070478."},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546853"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.11.018"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.02.015"},{"key":"ref38","doi-asserted-by":"crossref","unstructured":"M. Crochemore, C. S. Iliopoulos, J. Radoszewski, W. Rytter, J. Straszy\u0144ski, T. Wale\u0144, and W. Zuba, Internal quasiperiod queries, in 27th International Symposium on String Processing and Information Retrieval, SPIRE 2020, LNCS 12303, Springer-Verlag, Berlin, 2020, pp. 60\u201375, https:\/\/doi.org\/10.1007\/978-3-030-59212-7_5.","DOI":"10.1007\/978-3-030-59212-7_5"},{"key":"ref39","volume-title":"Jewels of Stringology","author":"Crochemore M.","year":"2003"},{"key":"ref40","unstructured":"D. Das, T. Kociumaka, and B. Saha, Improved approximation algorithms for Dyck edit distance and RNA folding, in 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, LIPIcs 229, Schloss Dagstuhl\u2013Leibniz Center for Informatics, Wadern, Germany, 2022, pp. 49:1\u201349:20, https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2022.49."},{"key":"ref41","doi-asserted-by":"crossref","unstructured":"R. Das, M. He, E. Kondratovsky, J. I. Munro, and K. Wu, Internal masked prefix sums and its connection to fully internal measurement queries, in 29th International Symposium on String Processing and Information Retrieval, SPIRE 2022, LNCS 13617, Springer-Verlag, Berlin, 2022, pp. 217\u2013232, https:\/\/doi.org\/10.1007\/978-3-031-20643-6_16.","DOI":"10.1007\/978-3-031-20643-6_16"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btv022"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1145\/355541.355547"},{"key":"ref44","doi-asserted-by":"crossref","unstructured":"M. Farach-Colton and S. Muthukrishnan, Perfect hashing for strings: Formalization and algorithms, in 7th Annual Symposium on Combinatorial Pattern Matching, CPM 1996, LNCS 1075, Springer-Verlag, Berlin, 1996, pp. 130\u2013140, https:\/\/doi.org\/10.1007\/3-540-61258-0_11.","DOI":"10.1007\/3-540-61258-0_11"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1145\/3369935"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1965-0174934-9"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1145\/3457389"},{"key":"ref48","unstructured":"Y. Gao, M. He, and Y. Nekrich, Fast preprocessing for optimal orthogonal range reporting and range successor with applications to text indexing, in 28th Annual European Symposium on Algorithms, ESA 2020, LIPIcs 173, Schloss Dagstuhl\u2013Leibniz Center for Informatics, Wadern, Germany, 2020, pp. 54:1\u201354:18, https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2020.54."},{"key":"ref49","doi-asserted-by":"crossref","unstructured":"P. Gawrychowski, Pattern matching in Lempel-Ziv compressed strings: Fast, simple, and deterministic, in 19th Annual European Symposium on Algorithms, ESA 2011, LNCS 6942, Springer-Verlag, Berlin, 2011, pp. 421\u2013432, https:\/\/doi.org\/10.1007\/978-3-642-23719-5_36.","DOI":"10.1007\/978-3-642-23719-5_36"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-017-9794-5"},{"key":"ref51","doi-asserted-by":"crossref","unstructured":"P. Gawrychowski, A. Karczmarz, T. Kociumaka, J.\u00a0\u0141\u0105cki, and P. Sankowski, Optimal dynamic strings, in Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, SIAM, Philadelphia, 2018, pp. 1509\u20131528, https:\/\/doi.org\/10.1137\/1.9781611975031.99.","DOI":"10.1137\/1.9781611975031.99"},{"key":"ref52","doi-asserted-by":"crossref","unstructured":"P. Gawrychowski, M. Lewenstein, and P. K. Nicholson, Weighted ancestors in suffix trees, in 22nd Annual European Symposium on Algorithms, ESA 2014, LNCS 8737, Springer-Verlag, Berlin, 2014, pp. 455\u2013466, https:\/\/doi.org\/10.1007\/978-3-662-44777-2_38.","DOI":"10.1007\/978-3-662-44777-2_38"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(81)90038-8"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-8667(03)00010-8"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1145\/362919.362934"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.09.009"},{"key":"ref57","unstructured":"C. S. Iliopoulos, T. Kociumaka, J. Radoszewski, W. Rytter, T. Wale\u0144, and W. Zuba, Linear-time computation of cyclic roots and cyclic covers of a string, in 34th Annual Symposium on Combinatorial Pattern Matching, CPM 2023, Marne-la-Vall\u00e9e, France, LIPIcs 259, Schloss Dagstuhl\u2013Leibniz Center for Informatics, Wadern, Germany, 2023, pp. 15:1\u201315:15, https:\/\/doi.org\/10.4230\/LIPICS.CPM.2023.15."},{"key":"ref58","doi-asserted-by":"crossref","unstructured":"G. Jacobson, Space-efficient static trees and graphs, in 30th Annual Symposium on Foundations of Computer Science, FOCS 1989, IEEE, New York, 1989, pp. 549\u2013554, https:\/\/doi.org\/10.1109\/SFCS.1989.63533.","DOI":"10.1109\/SFCS.1989.63533"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1145\/2631920"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1145\/2743014"},{"key":"ref61","doi-asserted-by":"crossref","unstructured":"C. Jin and J. Nogler, Quantum speed-ups for string synchronizing sets, longest common substring, and k-mismatch matching, in 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, SIAM, Philadelphia, 2023, pp. 5090\u20135121, https:\/\/doi.org\/10.1137\/1.9781611977554.ch186.","DOI":"10.1137\/1.9781611977554.ch186"},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1145\/1217856.1217858"},{"key":"ref63","doi-asserted-by":"publisher","DOI":"10.1147\/rd.312.0249"},{"key":"ref64","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.10.010"},{"key":"ref65","doi-asserted-by":"crossref","unstructured":"D. Kempa and T. Kociumaka, String synchronizing sets: Sublinear-time BWT construction and optimal LCE data structure, in 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, ACM, New York, 2019, pp. 756\u2013767, https:\/\/doi.org\/10.1145\/3313276.3316368.","DOI":"10.1145\/3313276.3316368"},{"key":"ref66","doi-asserted-by":"crossref","unstructured":"D. Kempa and T. Kociumaka, Resolution of the Burrows-Wheeler transform conjecture, in 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, IEEE, New York, 2020, pp. 1002\u20131013, https:\/\/doi.org\/10.1109\/FOCS46700.2020.00097.","DOI":"10.1109\/FOCS46700.2020.00097"},{"key":"ref67","doi-asserted-by":"crossref","unstructured":"D. Kempa and T. Kociumaka, Dynamic suffix array with polylogarithmic queries and updates, in 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, ACM, New York, 2022, pp. 1657\u20131670, https:\/\/doi.org\/10.1145\/3519935.3520061.","DOI":"10.1145\/3519935.3520061"},{"key":"ref68","doi-asserted-by":"crossref","unstructured":"D. Kempa and T. Kociumaka, Collapsing the hierarchy of compressed data structures: Suffix arrays in optimal compressed space, in 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, IEEE, New York, 2023, pp. 1877\u20131886, https:\/\/doi.org\/10.1109\/FOCS57990.2023.00114.","DOI":"10.1109\/FOCS57990.2023.00114"},{"key":"ref69","doi-asserted-by":"publisher","DOI":"10.1137\/0206024"},{"key":"ref70","unstructured":"T. Kociumaka, Minimal suffix and rotation of a substring in optimal time, in 27th Annual Symposium on Combinatorial Pattern Matching, CPM 2016, LIPIcs 54, Schloss Dagstuhl\u2013Leibniz Center for Informatics, Wadern, Germany, 2016, pp. 28:1\u201328:12, https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2016.28."},{"key":"ref71","unstructured":"T. Kociumaka, Efficient Data Structures for Internal Queries in Texts, Ph.D. thesis, University of Warsaw, 2018, https:\/\/www.mimuw.edu.pl\/\u223ckociumaka\/files\/phd.pdf."},{"key":"ref72","unstructured":"T. Kociumaka, R. Kundu, M. Mohamed, and S. P. Pissis, Longest unbordered factor in quasilinear time, in 29th International Symposium on Algorithms and Computation, ISAAC 2018, LIPIcs 123, Schloss Dagstuhl\u2013Leibniz Center for Informatics, Wadern, Germany, 2018, pp. 70:1\u201370:13, https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2018.70."},{"key":"ref73","doi-asserted-by":"crossref","unstructured":"T. Kociumaka, G. Navarro, and F. Olivares, Near-optimal search time in \\(\\delta\\)-optimal space, in 15th Latin American Symposium on Theoretical Informatics, LATIN 2022, LNCS 13568, Springer-Verlag, Berlin, 2022, pp. 88\u2013103, https:\/\/doi.org\/10.1007\/978-3-031-20624-5_6.","DOI":"10.1007\/978-3-031-20624-5_6"},{"key":"ref74","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2022.3224382"},{"key":"ref75","doi-asserted-by":"crossref","unstructured":"T. Kociumaka, J. Radoszewski, W. Rytter, and T. Wale\u0144, Efficient data structures for the factor periodicity problem, in 19th International Symposium on String Processing and Information Retrieval, SPIRE 2012, LNCS 7608, Springer-Verlag, Berlin, 2012, pp. 284\u2013294, https:\/\/doi.org\/10.1007\/978-3-642-34109-0_30.","DOI":"10.1007\/978-3-642-34109-0_30"},{"key":"ref76","doi-asserted-by":"crossref","unstructured":"T. Kociumaka, J. Radoszewski, W. Rytter, and T. Wale\u0144, Internal pattern matching queries in a text and applications, in 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, SIAM, Philadelphia, 2015, pp. 532\u2013551, https:\/\/doi.org\/10.1137\/1.9781611973730.36.","DOI":"10.1137\/1.9781611973730.36"},{"key":"ref77","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2017.10.004"},{"key":"ref78","doi-asserted-by":"crossref","unstructured":"R. M. Kolpakov and G. Kucherov, Finding maximal repetitions in a word in linear time, in 40th Annual Symposium on Foundations of Computer Science, FOCS 1999, IEEE, New York, 1999, pp. 596\u2013604, https:\/\/doi.org\/10.1109\/SFFCS.1999.814634.","DOI":"10.1109\/SFFCS.1999.814634"},{"key":"ref79","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2013.05.002"},{"key":"ref80","doi-asserted-by":"crossref","unstructured":"D. Kosolobov, F. Manea, and D. Nowotka, Detecting one-variable patterns, in 24th International Symposium on String Processing and Information Retrieval, SPIRE 2017, LNCS 10508, Springer-Verlag, Berlin, 2017, pp. 254\u2013270, https:\/\/doi.org\/10.1007\/978-3-319-67428-5_22.","DOI":"10.1007\/978-3-319-67428-5_22"},{"key":"ref81","doi-asserted-by":"crossref","unstructured":"S. Kuruppu, S. J. Puglisi, and J. Zobel, Relative Lempel-Ziv compression of genomes for large-scale storage and retrieval, in 17th International Symposium on String Processing and Information Retrieval, SPIRE 2010, LNCS 6393, Springer-Verlag, Berlin, 2010, pp. 201\u2013206, https:\/\/doi.org\/10.1007\/978-3-642-16321-0_20.","DOI":"10.1007\/978-3-642-16321-0_20"},{"key":"ref82","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90045-1"},{"key":"ref83","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bty191"},{"key":"ref84","first-page":"202","volume":"77","author":"Lyndon R. C.","year":"1954","journal-title":"Trans. Amer. Math. Soc."},{"key":"ref85","doi-asserted-by":"publisher","DOI":"10.1307\/mmj\/1028998766"},{"key":"ref86","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90051-6"},{"key":"ref87","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90092-2"},{"key":"ref88","doi-asserted-by":"publisher","DOI":"10.1007\/BF02522825"},{"key":"ref89","doi-asserted-by":"crossref","unstructured":"K. Mitani, T. Mieno, K. Seto, and T. Horiyama, Internal longest palindrome queries in optimal time, in 17th International Conference and Workshops on Algorithms and Computation, WALCOM 2023, LNCS 13973, Springer-Verlag, Berlin, 2023, pp. 127\u2013138, https:\/\/doi.org\/10.1007\/978-3-031-27051-2_12.","DOI":"10.1007\/978-3-031-27051-2_12"},{"key":"ref90","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603"},{"key":"ref91","unstructured":"J. H. Morris, Jr., and V. R. Pratt, A Linear Pattern-Matching Algorithm, Technical report 40, University of California, Berkeley, CA, 1970."},{"key":"ref92","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.11.011"},{"key":"ref93","doi-asserted-by":"crossref","unstructured":"Y. Nekrich and G. Navarro, Sorted range reporting, in 13th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2012, LNCS 7357, Springer-Verlag, Berlin, 2012, pp. 271\u2013282, https:\/\/doi.org\/10.1007\/978-3-642-31155-0_24.","DOI":"10.1007\/978-3-642-31155-0_24"},{"key":"ref94","doi-asserted-by":"crossref","unstructured":"M. Patil, R. Shah, and S. V. Thankachan, Faster range LCP queries, in 20th International Symposium on String Processing and Information Retrieval, SPIRE 2013, LNCS 8214, Springer-Verlag, Berlin, 2013, pp. 263\u2013270, https:\/\/doi.org\/10.1007\/978-3-319-02432-5_29.","DOI":"10.1007\/978-3-319-02432-5_29"},{"key":"ref95","doi-asserted-by":"crossref","unstructured":"M. P\u0103tra\u015fcu and M. Thorup, Dynamic integer sets with optimal rank, select, and predecessor search, in 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, IEEE, New York, 2014, pp. 166\u2013175, https:\/\/doi.org\/10.1109\/FOCS.2014.26.","DOI":"10.1109\/FOCS.2014.26"},{"key":"ref96","doi-asserted-by":"crossref","unstructured":"W. Plandowski and W. Rytter, Application of Lempel-Ziv encodings to the solution of words equations, in 25th International Colloquium on Automata, Languages and Programming, ICALP 1998, LNCS 1443, Springer-Verlag, Berlin, 1998, pp. 731\u2013742, https:\/\/doi.org\/10.1007\/BFb0055097.","DOI":"10.1007\/BFb0055097"},{"key":"ref97","doi-asserted-by":"publisher","DOI":"10.1145\/1698750.1698755"},{"key":"ref98","unstructured":"J. Radoszewski and J. Straszy\u0144ski, Efficient computation of 2-covers of a string, in 28th Annual European Symposium on Algorithms, ESA 2020, LIPIcs 173, Schloss Dagstuhl\u2013Leibniz Center for Informatics, Wadern, Germany, 2020, pp. 77:1\u201377:17, https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2020.77."},{"key":"ref99","doi-asserted-by":"crossref","unstructured":"E. Rivals and S. Rahmann, Combinatorics of periods in strings, in 28th International Colloquium on Automata, Languages and Programming, ICALP 2001 LNCS 2076, Springer-Verlag, Berlin, 2001, pp. 615\u2013626, https:\/\/doi.org\/10.1007\/3-540-48224-5.","DOI":"10.1007\/3-540-48224-5_51"},{"key":"ref100","unstructured":"E. Rivals, M. Sweering, and P. Wang, Convergence of the number of period sets in strings, in 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 LIPIcs 261, Schloss Dagstuhl\u2013Leibniz Center for Informatics, Wadern, Germany, 2023, pp. 100:1\u2013100:14, https:\/\/doi.org\/10.4230\/LIPICS.ICALP.2023.100."},{"key":"ref101","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth408"},{"key":"ref102","doi-asserted-by":"crossref","unstructured":"M. Ru\u017ei\u0107, Constructing efficient dictionaries in close to sorting time, in 35th International Colloquium on Automata, Languages and Programming, ICALP 2008 LNCS 5125, Springer-Verlag, Berlin, 2008, pp. 84\u201395, https:\/\/doi.org\/10.1007\/978-3-540-70575-8_8.","DOI":"10.1007\/978-3-540-70575-8_8"},{"key":"ref103","doi-asserted-by":"crossref","unstructured":"S. C. Sahinalp and U. Vishkin, On a parallel-algorithms method for string matching problems, in 2nd Italian Conference on Algorithms and Complexity, CIAC 1994, Rome, LNCS 778, Springer-Verlag, Berlin 1994, pp. 22\u201332, https:\/\/doi.org\/10.1007\/3-540-57811-0_3.","DOI":"10.1007\/3-540-57811-0_3"},{"key":"ref104","doi-asserted-by":"crossref","unstructured":"S. C. Sahinalp and U. Vishkin, Symmetry breaking for suffix tree construction, in 26th Annual ACM Symposium on Theory of Computing, STOC 1994, ACM, New York, 1994, pp. 300\u2013309, https:\/\/doi.org\/10.1145\/195058.195164.","DOI":"10.1145\/195058.195164"},{"key":"ref105","doi-asserted-by":"crossref","unstructured":"S. C. Sahinalp and U. Vishkin, Efficient approximate and dynamic matching of patterns using a labeling paradigm, in 37th IEEE Annual Symposium on Foundations of Computer Science, FOCS 1996, IEEE, New York, 1996, pp. 320\u2013328, https:\/\/doi.org\/10.1109\/SFCS.1996.548491.","DOI":"10.1109\/SFCS.1996.548491"},{"key":"ref106","doi-asserted-by":"crossref","unstructured":"S. Schleimer, D. S. Wilkerson, and A. Aiken, Winnowing: Local algorithms for document fingerprinting, in ACM SIGMOD International Conference on Management of Data, SIGMOD 2003, ACM, New York, 2003, pp. 76\u201385, https:\/\/doi.org\/10.1145\/872757.872770.","DOI":"10.1145\/872757.872770"},{"key":"ref107","doi-asserted-by":"crossref","unstructured":"D. Sorokina, J. Gehrke, S. Warner, and P. Ginsparg, Plagiarism detection in arXiv, in Sixth IEEE International Conference on Data Mining, ICDM 2006, IEEE, New York, 2006, pp. 1070\u20131075, https:\/\/doi.org\/10.1109\/ICDM.2006.126.","DOI":"10.1109\/ICDM.2006.126"},{"key":"ref108","first-page":"1","volume":"1","author":"Thue A.","year":"1912","journal-title":"Matematisk-naturvidenskabelig klasse"},{"key":"ref109","doi-asserted-by":"publisher","DOI":"10.1137\/0220002"},{"key":"ref110","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-023-10146-8"},{"key":"ref111","doi-asserted-by":"crossref","unstructured":"P. Weiner, Linear pattern matching algorithms, in 14th Annual Symposium on Switching and Automata Theory, SWAT 1973, IEEE, New York, 1973, pp. 1\u201311, https:\/\/doi.org\/10.1109\/SWAT.1973.13.","DOI":"10.1109\/SWAT.1973.13"},{"key":"ref112","doi-asserted-by":"publisher","DOI":"10.1186\/gb-2014-15-3-r46"},{"key":"ref113","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2015.09.002"},{"key":"ref114","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1977.1055714"},{"key":"ref115","doi-asserted-by":"publisher","DOI":"10.1109\/18.243444"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1567618","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:30:10Z","timestamp":1787337010000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1567618"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,14]]},"references-count":115,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10,31]]}},"alternative-id":["10.1137\/23M1567618"],"URL":"https:\/\/doi.org\/10.1137\/23m1567618","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,14]]}}}