{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,23]],"date-time":"2026-09-23T07:00:49Z","timestamp":1790146849603,"version":"4.0.1"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T00:00:00Z","timestamp":1788220800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,9,11]],"date-time":"2026-09-11T00:00:00Z","timestamp":1789084800000},"content-version":"vor","delay-in-days":10,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["101039208 (REGINDEX)"],"award-info":[{"award-number":["101039208 (REGINDEX)"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"PhD Fellowship","award":["FR (1117322N), Research Foundation \u2013 Flanders (FWO)"],"award-info":[{"award-number":["FR (1117322N), Research Foundation \u2013 Flanders (FWO)"]}]},{"name":"NSERC Discovery Grant","award":["RGPIN-07185-2020"],"award-info":[{"award-number":["RGPIN-07185-2020"]}]},{"DOI":"10.13039\/100031478","name":"NextGenerationEU","doi-asserted-by":"publisher","award":["rogramme PNRR ECS00000017 Tuscany Health Ecosystem (CUP: I53C22000780001)"],"award-info":[{"award-number":["rogramme PNRR ECS00000017 Tuscany Health Ecosystem (CUP: I53C22000780001)"]}],"id":[{"id":"10.13039\/100031478","id-type":"DOI","asserted-by":"publisher"}]},{"name":"PAN-HUB project","award":["Italian Ministry of Health (CUP: I53C22001300001)"],"award-info":[{"award-number":["Italian Ministry of Health (CUP: I53C22001300001)"]}]},{"name":"Scholarship ANID Subdirecci\u00f3n de Capital Humano\/Doctorado Nacional\/","award":["2021-21210579, ANID, Chile"],"award-info":[{"award-number":["2021-21210579, ANID, Chile"]}]},{"name":"Basal Funds","award":["FB0001, ANID, Chile"],"award-info":[{"award-number":["FB0001, ANID, Chile"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2026,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    The Suffix Array is a classic text index enabling on-line pattern matching queries via simple binary search. The main drawback of the Suffix Array is that it takes linear space in the text\u2019s length, even when the text itself is extremely compressible. Several works in the literature showed that the Suffix Array can be compressed, but they all rely on complex succinct data structures which in practice tend to exhibit poor cache locality and thus significantly slow down queries. In this paper, we propose a new simple and very efficient solution to this problem by presenting the\n                    <jats:italic>Suffixient Array<\/jats:italic>\n                    : a tiny subset of the Suffix Array\n                    <jats:italic>sufficient<\/jats:italic>\n                    to locate on-line one pattern occurrence (in general, all its Maximal Exact Matches) via binary search, provided that random access to the text is available. We prove that: (i) the Suffixient Array length\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{\\chi }$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>\u03c7<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is a strong repetitiveness measure, (ii) unlike most existing repetition-aware indexes such as the\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{r}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>r<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -index, our new index is efficient in the I\/O model, and (iii) Suffixient Arrays can be computed in linear time and compressed working space. We show experimentally that, when using well-established compressed random access data structures on repetitive collections, the Suffixient Array\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{\\textrm{sA}}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mtext>sA<\/mml:mtext>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is\n                    <jats:italic>simultaneously<\/jats:italic>\n                    (i) faster and orders of magnitude smaller than the Suffix Array and (ii) smaller and\n                    <jats:italic>one to two orders of magnitude faster<\/jats:italic>\n                    than the\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{r}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>r<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -index. With an average pattern matching query time as low as 3.5 ns per character, our new index gets very close to the ultimate lower bound: the RAM throughput of our workstation (1.18 ns per character).\n                  <\/jats:p>","DOI":"10.1007\/s00224-026-10287-6","type":"journal-article","created":{"date-parts":[[2026,9,11]],"date-time":"2026-09-11T11:19:24Z","timestamp":1789125564000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Suffixient Arrays: A New Efficient Suffix Array Compression Technique"],"prefix":"10.1007","volume":"70","author":[{"given":"Davide","family":"Cenzato","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lore","family":"Depuydt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sung-Hwan","family":"Kim","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giovanni","family":"Manzini","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Francisco","family":"Olivares","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicola","family":"Prezza","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,9,11]]},"reference":[{"key":"10287_CR1","doi-asserted-by":"publisher","unstructured":"Cenzato, D., Olivares, F., Prezza, N.: On computing the smallest suffixient set. In: Proceedings of the 31st International Symposium on String Processing and Information Retrieval, pp. 73\u201387 (2024). https:\/\/doi.org\/10.1007\/978-3-031-72200-4_6","DOI":"10.1007\/978-3-031-72200-4_6"},{"key":"10287_CR2","unstructured":"Depuydt, L., Gagie, T., Langmead, B., Manzini, G., Prezza, N.: Suffixient Sets. arxiv:2312.01359 (2024)"},{"issue":"2","key":"10287_CR3","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1145\/3434399","volume":"54","author":"G Navarro","year":"2022","unstructured":"Navarro, G.: Indexing highly repetitive string collections, part I: Repetitiveness measures. ACM Comput. Surv. 54(2), 29\u201312931 (2022). https:\/\/doi.org\/10.1145\/3434399","journal-title":"ACM Comput. Surv."},{"issue":"2","key":"10287_CR4","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1145\/3432999","volume":"54","author":"G Navarro","year":"2022","unstructured":"Navarro, G.: Indexing highly repetitive string collections, Part II: Compressed indexes. ACM Comput. Surv. 54(2), 26\u201312631 (2022). https:\/\/doi.org\/10.1145\/3432999","journal-title":"ACM Comput. Surv."},{"key":"10287_CR5","unstructured":"DNA Sequencing Costs: Data. https:\/\/www.genome.gov\/about-genomics\/fact-sheets\/DNA-Sequencing-Costs-Data. Accessed: (07 Jan 2025)"},{"issue":"6","key":"10287_CR6","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1016\/j.gde.2005.09.006","volume":"15","author":"D Medini","year":"2005","unstructured":"Medini, D., Donati, C., Tettelin, H., Masignani, V., Rappuoli, R.: The microbial pan-genome. Curr. Opin. Genetics Dev. 15(6), 589\u2013594 (2005). https:\/\/doi.org\/10.1016\/j.gde.2005.09.006","journal-title":"Curr. Opin. Genetics Dev."},{"issue":"7906","key":"10287_CR7","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1038\/s41586-022-04601-8","volume":"604","author":"T Wang","year":"2022","unstructured":"Wang, T., Antonacci-Fulton, L., Howe, K., Lawson, H.A., Lucas, J.K., Phillippy, A.M., Popejoy, A.B., Asri, M., Carson, C., Chaisson, M.J., et al.: The human pangenome project: A global resource to map genomic diversity. Nature 604(7906), 437\u2013446 (2022). https:\/\/doi.org\/10.1038\/s41586-022-04601-8","journal-title":"Nature"},{"key":"10287_CR8","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1038\/35035083","volume":"407","author":"D Altshuler","year":"2000","unstructured":"Altshuler, D., Pollara, V.J., Cowles, C.R., Etten, W.J.V., Baldwin, J., Linton, L., Lander, E.S.: An SNP map of the human genome generated by reduced representation shotgun sequencing. Nature 407, 513\u2013516 (2000). https:\/\/doi.org\/10.1038\/35035083","journal-title":"Nature"},{"key":"10287_CR9","doi-asserted-by":"publisher","unstructured":"Consortium, T.G.P.: A global reference for human genetic variation. Nature 526(7571), 68\u201374 (2015). https:\/\/doi.org\/10.1038\/nature15393","DOI":"10.1038\/nature15393"},{"key":"10287_CR10","unstructured":"Manber, U., Myers, G.: Suffix arrays: A new method for on-line string searches. In: First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 319\u2013327. ACM (1990)"},{"key":"10287_CR11","doi-asserted-by":"publisher","unstructured":"Baeza-Yates, R.A., Gonnet, G.H.: A new approach to text searching. In: Proceedings of the 12th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. SIGIR \u201989, pp. 168\u2013175. ACM, New York, NY, USA (1989). https:\/\/doi.org\/10.1145\/75334.75352","DOI":"10.1145\/75334.75352"},{"key":"10287_CR12","first-page":"82","volume":"66","author":"GH Gonnet","year":"1992","unstructured":"Gonnet, G.H., Baeza-Yates, R.A., Snider, T.: New indices for text: Pat trees and pat arrays. Inf. Retrieval: Data Struc. Algorithms 66, 82 (1992)","journal-title":"Inf. Retrieval: Data Struc. Algorithms"},{"issue":"3","key":"10287_CR13","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"23","author":"J Ziv","year":"1977","unstructured":"Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Trans. Inf. Theory 23(3), 337\u2013343 (1977)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"11","key":"10287_CR14","doi-asserted-by":"publisher","first-page":"1722","DOI":"10.1109\/5.892708","volume":"88","author":"NJ Larsson","year":"2000","unstructured":"Larsson, N.J., Moffat, A.: Off-line dictionary-based compression. Proc. IEEE 88(11), 1722\u20131732 (2000). https:\/\/doi.org\/10.1109\/5.892708","journal-title":"Proc. IEEE"},{"key":"10287_CR15","doi-asserted-by":"publisher","unstructured":"Ferragina, P., Manzini, G.: Opportunistic data structures with applications. In: Proceedings 41st Annual Symposium on Foundations of Computer Science, pp. 390\u2013398 (2000). https:\/\/doi.org\/10.1109\/SFCS.2000.892127","DOI":"10.1109\/SFCS.2000.892127"},{"key":"10287_CR16","doi-asserted-by":"publisher","unstructured":"Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. In: Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing (STOC), pp. 397\u2013406 (2000). https:\/\/doi.org\/10.1145\/335305.33535","DOI":"10.1145\/335305.33535"},{"issue":"1","key":"10287_CR17","first-page":"40","volume":"12","author":"V M\u00e4kinen","year":"2005","unstructured":"M\u00e4kinen, V., Navarro, G.: Succinct suffix arrays based on run-length encoding. Nordic J. Comput. 12(1), 40\u201366 (2005)","journal-title":"Nordic J. Comput."},{"key":"10287_CR18","doi-asserted-by":"publisher","unstructured":"Gagie, T., Navarro, G., Prezza, N.: Fully functional suffix trees and optimal text searching in BWT-runs bounded space. J. ACM. 67(1) (2020). https:\/\/doi.org\/10.1145\/3375890","DOI":"10.1145\/3375890"},{"key":"10287_CR19","doi-asserted-by":"publisher","unstructured":"Puglisi, S.J., Zhukova, B.: Smaller RLZ-compressed suffix arrays. In: 2021 Data Compression Conference (DCC), pp. 213\u2013222. IEEE (2021). https:\/\/doi.org\/10.1109\/DCC50243.2021.00029","DOI":"10.1109\/DCC50243.2021.00029"},{"key":"10287_CR20","doi-asserted-by":"publisher","unstructured":"Depuydt, L., Renders, L., Vyver, S., Veys, L., Gagie, T., Fostier, J.: b-move: Faster Bidirectional Character Extensions in a Run-Length Compressed Index. In: Pissis, S.P., Sung, W.-K. (eds.) 24th International Workshop on Algorithms in Bioinformatics (WABI 2024). Leibniz International Proceedings in Informatics (LIPIcs), vol. 312, pp. 10\u201311018. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2024). https:\/\/doi.org\/10.4230\/LIPIcs.WABI.2024.10","DOI":"10.4230\/LIPIcs.WABI.2024.10"},{"key":"10287_CR21","unstructured":"Li, H.: Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM. arxiv:1303.3997 (2013)"},{"key":"10287_CR22","doi-asserted-by":"publisher","unstructured":"Bannai, H., Gagie, T., I., T.: Refining r-index. Theoret. Comput. Sci. 812, 92\u2013108 (2020). https:\/\/doi.org\/10.1016\/j.tcs.2019.08.005","DOI":"10.1016\/j.tcs.2019.08.005"},{"issue":"2","key":"10287_CR23","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1089\/CMB.2021.0290","volume":"29","author":"M Rossi","year":"2022","unstructured":"Rossi, M., Oliva, M., Langmead, B., Gagie, T., Boucher, C.: MONI: A pangenomic index for finding maximal exact matches. J. Comput. Biol. 29(2), 169\u2013187 (2022). https:\/\/doi.org\/10.1089\/CMB.2021.0290","journal-title":"J. Comput. Biol."},{"key":"10287_CR24","doi-asserted-by":"publisher","unstructured":"Boucher, C., Gagie, T., I, T., K\u00f6ppl, D., Langmead, B., Manzini, G., Navarro, G., Pacheco, A., Rossi, M.: PHONI: Streamed Matching Statistics with Multi-Genome References. In: Data Compression Conference (DCC), pp. 193\u2013202 (2021). https:\/\/doi.org\/10.1109\/DCC50243.2021.00027","DOI":"10.1109\/DCC50243.2021.00027"},{"key":"10287_CR25","doi-asserted-by":"publisher","unstructured":"Nishimoto, T., Tabei, Y.: Optimal-time queries on BWT-runs compressed indexes. In: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), pp. 101\u20131. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.101","DOI":"10.4230\/LIPIcs.ICALP.2021.101"},{"key":"10287_CR26","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1137\/130936889","volume":"44","author":"P Bille","year":"2015","unstructured":"Bille, P., Landau, G.M., Raman, R., Sadakane, K., Satti, S.R., Weimann, O.: Random access to grammar-compressed strings and trees. SIAM J. Comput. 44, 513\u2013539 (2015). https:\/\/doi.org\/10.1137\/130936889","journal-title":"SIAM J. Comput."},{"key":"10287_CR27","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.tcs.2012.02.006","volume":"483","author":"S Kreft","year":"2013","unstructured":"Kreft, S., Navarro, G.: On compressing and indexing repetitive sequences. Theoret. Comput. Sci. 483, 115\u2013133 (2013). https:\/\/doi.org\/10.1016\/j.tcs.2012.02.006","journal-title":"Theoret. Comput. Sci."},{"key":"10287_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2020.11.002","volume":"117","author":"D Belazzougui","year":"2021","unstructured":"Belazzougui, D., C\u00e1ceres, M., Gagie, T., Gawrychowski, P., K\u00e4rkk\u00e4inen, J., Navarro, G., Ord\u00f3\u00f1ez, A., Puglisi, S.J., Tabei, Y.: Block trees. J. Comput. Syst. Sci. 117, 1\u201322 (2021). https:\/\/doi.org\/10.1016\/j.jcss.2020.11.002","journal-title":"J. Comput. Syst. Sci."},{"key":"10287_CR29","doi-asserted-by":"publisher","unstructured":"Kuruppu, S., Puglisi, S.J., Zobel, J.: Relative Lempel-Ziv compression of genomes for large-scale storage and retrieval. In: International Symposium on String Processing and Information Retrieval, pp. 201\u2013206. Springer, (2010). https:\/\/doi.org\/10.1007\/978-3-642-16321-0_20","DOI":"10.1007\/978-3-642-16321-0_20"},{"key":"10287_CR30","doi-asserted-by":"publisher","unstructured":"Bentley, J.W., Gibney, D., Thankachan, S.V.: On the complexity of BWT-runs minimization via alphabet reordering. In: Proceedings of the 28th Annual European Symposium on Algorithms (ESA 2020). LIPIcs, vol. 173, pp. 15\u201311513 (2020). https:\/\/doi.org\/10.4230\/LIPICS.ESA.2020.15","DOI":"10.4230\/LIPICS.ESA.2020.15"},{"key":"10287_CR31","doi-asserted-by":"publisher","unstructured":"Kempa, D., Prezza, N.: At the roots of dictionary compression: string attractors. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018). STOC 2018, pp. 827\u2013840. Association for Computing Machinery, New York, NY, USA (2018). https:\/\/doi.org\/10.1145\/3188745.3188814 . https:\/\/doi.org\/10.1145\/3188745.3188814","DOI":"10.1145\/3188745.3188814"},{"key":"10287_CR32","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Monotone minimal perfect hashing: searching a sorted table with $$o(1)$$ accesses. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 785\u2013794 (2009). https:\/\/dl.acm.org\/doi\/10.5555\/1496770.1496856","DOI":"10.1137\/1.9781611973068.86"},{"issue":"1","key":"10287_CR33","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1186\/S13015-019-0148-5","volume":"14","author":"C Boucher","year":"2019","unstructured":"Boucher, C., Gagie, T., Kuhnle, A., Langmead, B., Manzini, G., Mun, T.: Prefix-free parsing for building big BWTs. Algorithms Mol. Biol. 14(1), 13\u201311315 (2019). https:\/\/doi.org\/10.1186\/S13015-019-0148-5","journal-title":"Algorithms Mol. Biol."},{"key":"10287_CR34","doi-asserted-by":"crossref","unstructured":"Li, H.: Exploring single-sample snp and indel calling with whole-genome de novo assembly. Bioinformatics 28(14), 1838\u20131844 (2012). https:\/\/doi.org\/10.1093\/bioinformatics\/bts280","DOI":"10.1093\/bioinformatics\/bts280"},{"issue":"5","key":"10287_CR35","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber, U., Myers, G.: Suffix arrays: A new method for on-line string searches. SIAM J. Comput. 22(5), 935\u2013948 (1993). https:\/\/doi.org\/10.1137\/0222058","journal-title":"SIAM J. Comput."},{"key":"10287_CR36","doi-asserted-by":"publisher","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: Proceedings of the 14th Annual Symposium on Switching and Automata Theory, pp. 1\u201311 (1973). https:\/\/doi.org\/10.1109\/SWAT.1973.13","DOI":"10.1109\/SWAT.1973.13"},{"key":"10287_CR37","unstructured":"Burrows, M., Wheeler, D.J.: A block sorting lossless data compression algorithm, Digital Equipment Corporation (1994). (124 Technical Report)"},{"key":"10287_CR38","doi-asserted-by":"publisher","unstructured":"Bentley, J.W., Gibney, D., Thankachan, S.V.: On the Complexity of BWT-Runs Minimization via Alphabet Reordering. In: 28th Annual European Symposium on Algorithms (ESA 2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2020.15","DOI":"10.4230\/LIPIcs.ESA.2020.15"},{"key":"10287_CR39","doi-asserted-by":"publisher","unstructured":"Sir\u00e9n, J., V\u00e4lim\u00e4ki, N., M\u00e4kinen, V., Navarro, G.: Run-length compressed indexes are superior for highly repetitive sequence collections. In: Amir, A., Turpin, A., Moffat, A. (eds.) String Processing and Information Retrieval, 15th International Symposium, SPIRE 2008, Melbourne, Australia, November 10-12, 2008. Proceedings. Lecture Notes in Computer Science, vol. 5280, pp. 164\u2013175. Springer, (2008). https:\/\/doi.org\/10.1007\/978-3-540-89097-3_17","DOI":"10.1007\/978-3-540-89097-3_17"},{"key":"10287_CR40","doi-asserted-by":"publisher","unstructured":"Boldi, P., Vigna, S.: Kings, Name Days, Lazy Servants and Magic. In: Ito, H., Leonardi, S., Pagli, L., Prencipe, G. (eds.) 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), vol. 100, pp. 10\u201311013. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2018). https:\/\/doi.org\/10.4230\/LIPIcs.FUN.2018.10","DOI":"10.4230\/LIPIcs.FUN.2018.10"},{"key":"10287_CR41","doi-asserted-by":"publisher","unstructured":"Bal\u00e1\u017e, A., Gagie, T., Goga, A., Heumos, S., Navarro, G., Petescia, A., Sir\u00e9n, J.: Wheeler maps. In: Soto, J.A., Wiese, A. (eds.) LATIN 2024: Theoretical Informatics, pp. 178\u2013192. Springer, Cham (2024). https:\/\/doi.org\/10.1007\/978-3-031-55598-5_12","DOI":"10.1007\/978-3-031-55598-5_12"},{"key":"10287_CR42","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/j.jcss.2017.01.002","volume":"86","author":"P Bille","year":"2017","unstructured":"Bille, P., G\u00f8rtz, I.L., Cording, P.H., Sach, B., Vildh\u00f8j, H.W., Vind, S.: Fingerprints in compressed strings. J. Comput. Syst. Sci. 86, 171\u2013180 (2017). https:\/\/doi.org\/10.1016\/j.jcss.2017.01.002","journal-title":"J. Comput. Syst. Sci."},{"issue":"7","key":"10287_CR43","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/362686.362692","volume":"13","author":"BH Bloom","year":"1970","unstructured":"Bloom, B.H.: Space\/time trade-offs in hash coding with allowable errors. Commun. ACM 13(7), 422\u2013426 (1970). https:\/\/doi.org\/10.1145\/362686.362692","journal-title":"Commun. ACM"},{"key":"10287_CR44","doi-asserted-by":"crossref","unstructured":"Li, H.: Exploring single-sample SNP and INDEL calling with whole-genome de novo assembly. Bioinformatics 28(14), 1838\u20131844 (2012). https:\/\/doi.org\/10.1093\/bioinformatics\/bts280","DOI":"10.1093\/bioinformatics\/bts280"},{"key":"10287_CR45","doi-asserted-by":"publisher","unstructured":"Gagie, T.: How to find long maximal exact matches and ignore short ones. In: International Conference on Developments in Language Theory, pp. 131\u2013140 (2024). https:\/\/doi.org\/10.1007\/978-3-031-66159-4_10","DOI":"10.1007\/978-3-031-66159-4_10"},{"issue":"4","key":"10287_CR46","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1089\/CMB.2019.0309","volume":"27","author":"A Kuhnle","year":"2020","unstructured":"Kuhnle, A., Mun, T., Boucher, C., Gagie, T., Langmead, B., Manzini, G.: Efficient construction of a complete index for pan-genomics read alignment. J. Comput. Biol. 27(4), 500\u2013513 (2020). https:\/\/doi.org\/10.1089\/CMB.2019.0309","journal-title":"J. Comput. Biol."},{"issue":"51","key":"10287_CR47","doi-asserted-by":"publisher","first-page":"5354","DOI":"10.1016\/j.tcs.2009.09.012","volume":"410","author":"J Fischer","year":"2009","unstructured":"Fischer, J., M\u00e4kinen, V., Navarro, G.: Faster entropy-bounded compressed suffix trees. Theoret. Comput. Sci. 410(51), 5354\u20135364 (2009)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"10287_CR48","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1006\/jagm.1993.1018","volume":"14","author":"O Berkman","year":"1993","unstructured":"Berkman, O., Schieber, B., Vishkin, U.: Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values. J. Algorithms 14(3), 344\u2013370 (1993). https:\/\/doi.org\/10.1006\/jagm.1993.1018","journal-title":"J. Algorithms"},{"issue":"4","key":"10287_CR49","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/2629339","volume":"11","author":"D Belazzougui","year":"2015","unstructured":"Belazzougui, D., Navarro, G.: Optimal lower and upper bounds for representing sequences. ACM Trans. Algorithms 11(4), 31\u201313121 (2015). https:\/\/doi.org\/10.1145\/2629339","journal-title":"ACM Trans. Algorithms"},{"key":"10287_CR50","doi-asserted-by":"publisher","unstructured":"Navarro, G., Romana, G., Urbina, C.: Smallest suffixient sets as a repetitiveness measure. In: Proceedings of the 32nd International Symposium on String Processing and Information Retrieval, pp. 217\u2013232 (2025). https:\/\/doi.org\/10.1007\/978-3-032-05228-5_18","DOI":"10.1007\/978-3-032-05228-5_18"},{"issue":"6","key":"10287_CR51","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1145\/3531445","volume":"65","author":"D Kempa","year":"2022","unstructured":"Kempa, D., Kociumaka, T.: Resolution of the Burrows-Wheeler transform conjecture. Commun. ACM 65(6), 91\u201398 (2022). https:\/\/doi.org\/10.1145\/3531445","journal-title":"Commun. ACM"},{"key":"10287_CR52","doi-asserted-by":"publisher","unstructured":"Lam, T.W., Li, R., Tam, A., Wong, S., Wu, E., Yiu, S.: High throughput short read alignment via bi-directional BWT. In: IEEE International Conference on Bioinformatics and Biomedicine, pp. 31\u201336 (2009). https:\/\/doi.org\/10.1109\/BIBM.2009.42","DOI":"10.1109\/BIBM.2009.42"},{"key":"10287_CR53","doi-asserted-by":"publisher","unstructured":"Kucherov, G., Salikhov, K., Tsur, D.: Approximate String Matching Using a Bidirectional Index. In: Kulikov, A.S., Kuznetsov, S.O., Pevzner, P. (eds.) Combinatorial Pattern Matching, pp. 222\u2013231. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-07566-2_23","DOI":"10.1007\/978-3-319-07566-2_23"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10287-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-026-10287-6","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10287-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,9,23]],"date-time":"2026-09-23T06:12:36Z","timestamp":1790143956000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-026-10287-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,9]]},"references-count":53,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,9]]}},"alternative-id":["10287"],"URL":"https:\/\/doi.org\/10.1007\/s00224-026-10287-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,9]]},"assertion":[{"value":"17 March 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 June 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 September 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare no competing interests.","order":1,"name":"Ethics","label":"Competing interests","group":{"name":"EthicsHeading","label":"Declarations"}}],"article-number":"50"}}