{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,5]],"date-time":"2026-11-05T03:48:13Z","timestamp":1793850493684,"version":"4.6.1"},"reference-count":95,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2026,4,30]]},"abstract":"<jats:p>\n                    In the classic Longest Common Substring (LCS) problem, we are given two strings\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( S \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    and\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( T \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    of total length\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( n \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    over an alphabet of size\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\sigma\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    , and we are asked to find a longest string occurring as a fragment of both\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( S \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    \u00a0and\u00a0\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( T \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    . Weiner, in his seminal paper that introduced the suffix tree, presented an\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal{O}(n\\log\\sigma)\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -time algorithm for the LCS problem [SWAT 1973]. For polynomially-bounded integer alphabets, the linear-time construction of suffix trees by Farach yielded an\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal{O}(n)\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -time algorithm for the LCS problem [FOCS 1997]. However, for small alphabets, this is not necessarily optimal for the LCS problem in the word RAM model of computation, in which the strings can be stored in\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal{O}(n\\log\\sigma\/\\log n)\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    space and read in\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal{O}(n\\log\\sigma\/\\log n)\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    time. We show that we can compute an LCS of two strings in time\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal{O}(n\\log\\sigma\/\\sqrt{\\log n})\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    in the word RAM model, which is sublinear in\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( n \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    if\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\sigma=2^{o(\\sqrt{\\log n})}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    (in particular, if\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\sigma=\\mathcal{O}(1)\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    ), using optimal space\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal{O}(n\\log\\sigma\/\\log n)\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    . In fact, it was recently shown that this result is conditionally optimal [Kempa and Kociumaka, STOC 2025]. The same complexity can be achieved for computing an LCS of\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\lambda=\\mathcal{O}(\\sqrt{\\log n}\/\\log\\log n)\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    input strings of total length\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( n \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    .\n                  <\/jats:p>\n                  <jats:p>\n                    We then lift our ideas to the problem of computing a\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( k \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -mismatch LCS, which has received considerable attention in recent years. In this problem, the aim is to compute a longest substring of\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( S \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    that occurs in\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( T \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    with at most\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( k \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    mismatches. Flouri et al. showed how to compute a 1-mismatch LCS in\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal{O}(n\\log n)\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    time [IPL 2015]. Thankachan et al. extended this result to computing a\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( k \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -mismatch LCS in\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal{O}(n\\log^{k}n)\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    time for\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(k=\\mathcal{O}(1)\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    [J. Comput. Biol. 2016]. We show an\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal{O}(n\\log^{k-0.5}n)\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -time algorithm, for any constant integer\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(k &gt; 0\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    and\n                    <jats:italic toggle=\"yes\">irrespective<\/jats:italic>\n                    of the alphabet size, using\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal{O}(n)\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    space as the previous approaches. We thus notably break through the well-known\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(n\\log^{k}n\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    barrier, which stems from a recursive heavy-path decomposition technique that was first introduced in the seminal paper of Cole et al. for string indexing with\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( k \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    errors [STOC 2004]. As a by-product, we improve upon the algorithm of Charalampopoulos et al. [CPM 2018] for computing a\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( k \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -mismatch LCS in the case when the output\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( k \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -mismatch LCS is sufficiently long.\n                  <\/jats:p>","DOI":"10.1145\/3774754","type":"journal-article","created":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T13:45:18Z","timestamp":1762350318000},"page":"1-47","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Faster Algorithms for Longest Common Substring"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6024-1557","authenticated-orcid":false,"given":"Panagiotis","family":"Charalampopoulos","sequence":"first","affiliation":[{"name":"King\u2019s College London, London, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2477-1702","authenticated-orcid":false,"given":"Tomasz","family":"Kociumaka","sequence":"additional","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":false,"given":"Jakub","family":"Radoszewski","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warsaw, Poland and Samsung R&amp;D Institute Poland, Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1445-1932","authenticated-orcid":false,"given":"Solon P.","family":"Pissis","sequence":"additional","affiliation":[{"name":"CWI, Amsterdam, The Netherlands and Vrije Universiteit, Amsterdam, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,2,6]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.17"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-022-00955-7"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-022-01092-X"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CPM.2018.11"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-67428-5_2"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00744-0"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236460"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-00479-8_3"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.39"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","unstructured":"Maxim A. Babenko and Tatiana Starikovskaya. 2011. Computing the longest common substring with one mismatch. Problems of Information Transmission 47 1 (2011) 28\u201333. DOI: 10.1134\/S0032946011010030","DOI":"10.1134\/S0032946011010030"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","unstructured":"Ricardo A. Baeza-Yates. 1989. Improved string searching. Software: Practice and Experience 19 3 (1989) 257\u2013271. DOI: 10.1002\/spe.4380190305","DOI":"10.1002\/spe.4380190305"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2023.14"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1011032"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-012-9726-3"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19222-7_10"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9873-9"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2635816"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2629339"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.06.013"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CPM.2020.5"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/10719839_9"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02441-2_11"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2010.09.003"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CPM.2017.6"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31265-6_7"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.69"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45123-4_33"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/322123.322127"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44888-8_5"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-95891-8_25"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9263-2"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2011.04.004"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.15"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CPM.2018.23"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CPM.2023.8"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.27"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-022-00934-Y"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","unstructured":"Panagiotis Charalampopoulos Costas S. Iliopoulos Chang Liu and Solon P. Pissis. 2020. Property suffix array with applications in indexing weighted sequences. Journal of Experimental Algorithmics 25 (2020) 1\u201316. DOI: 10.1145\/3385898","DOI":"10.1145\/3385898"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2021.30"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2020.07.003"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00095"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CPM.2022.20"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60044-2_33"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.70"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00080-6"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007374"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700370527"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1017\/cbo9780511546853"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.06.029"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-43980-3_14"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.63"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646102"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","unstructured":"Nathan J. Fine and Herbert S. Wilf. 1965. Uniqueness theorems for periodic functions. Proceedings of the American Mathematical Society 16 1 (1965) 109\u2013114. DOI: 10.1090\/S0002-9939-1965-0174934-9","DOI":"10.1090\/S0002-9939-1965-0174934-9"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2015.03.006"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45735-6_5"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(03)00296-5"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90014-5"},{"key":"e_1_3_2_59_2","volume-title":"Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG \u201913)","author":"Gagie Travis","year":"2013","unstructured":"Travis Gagie, Pawel Gawrychowski, and Yakov Nekrich. 2013. Heaviest induced ancestors and longest common substrings. In Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG \u201913). Carleton University, Ottawa, Canada. Retrieved from http:\/\/cccg.ca\/proceedings\/2013\/papers\/paper_29.pdf"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.07.002"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CPM.2020.16"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2015.03.003"},{"key":"e_1_3_2_63_2","first-page":"841","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Grossi Roberto","year":"2003","unstructured":"Roberto Grossi, Ankur Gupta, and Jeffrey Scott Vitter. 2003. High-order entropy-compressed text indexes. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, 841\u2013850. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=644108.644250"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.09.001"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-56024-6_19"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.11.022"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_2_69_2","doi-asserted-by":"publisher","DOI":"10.1145\/3672395"},{"key":"e_1_3_2_70_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316368"},{"key":"e_1_3_2_71_2","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718291"},{"key":"e_1_3_2_72_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-76336-9_14"},{"key":"e_1_3_2_73_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00548-x"},{"key":"e_1_3_2_74_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_50"},{"key":"e_1_3_2_75_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814634"},{"key":"e_1_3_2_76_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.JDA.2005.01.006"},{"key":"e_1_3_2_77_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-022-01066-Z"},{"key":"e_1_3_2_78_2","doi-asserted-by":"publisher","DOI":"10.1145\/214438.214445"},{"key":"e_1_3_2_79_2","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"e_1_3_2_80_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.TCS.2008.12.016"},{"key":"e_1_3_2_81_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.26"},{"key":"e_1_3_2_82_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-019-00637-X"},{"key":"e_1_3_2_83_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CPM.2020.24"},{"key":"e_1_3_2_84_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.11.011"},{"key":"e_1_3_2_85_2","doi-asserted-by":"publisher","DOI":"10.1137\/140998949"},{"key":"e_1_3_2_86_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0030778"},{"key":"e_1_3_2_87_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38905-4_22"},{"key":"e_1_3_2_88_2","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-024X(199707)27:7<851::AID-SPE108>3.0.CO;2-D"},{"key":"e_1_3_2_89_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-89929-9_14"},{"key":"e_1_3_2_90_2","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2015.0235"},{"key":"e_1_3_2_91_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2010.08.002"},{"key":"e_1_3_2_92_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0029808"},{"key":"e_1_3_2_93_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(77)90031-X"},{"key":"e_1_3_2_94_2","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1973.13"},{"key":"e_1_3_2_95_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90075-3"},{"key":"e_1_3_2_96_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797322425"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3774754","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T14:12:46Z","timestamp":1770732766000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3774754"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,6]]},"references-count":95,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4,30]]}},"alternative-id":["10.1145\/3774754"],"URL":"https:\/\/doi.org\/10.1145\/3774754","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,6]]},"assertion":[{"value":"2024-09-12","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-28","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-02-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}