{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T11:46:35Z","timestamp":1757591195336,"version":"3.37.3"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,9,16]],"date-time":"2024-09-16T00:00:00Z","timestamp":1726444800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,16]],"date-time":"2024-09-16T00:00:00Z","timestamp":1726444800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100021856","name":"Ministero dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["MUR - FSE REACT EU - PON R&I 2014-2020"],"award-info":[{"award-number":["MUR - FSE REACT EU - PON R&I 2014-2020"]}],"id":[{"id":"10.13039\/501100021856","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"publisher","award":["956229","872539","872539"],"award-info":[{"award-number":["956229","872539","872539"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100019926","name":"Nederlandse Organisatie voor Toegepast Natuurwetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["OCENW.GROOT.2019.015"],"award-info":[{"award-number":["OCENW.GROOT.2019.015"]}],"id":[{"id":"10.13039\/501100019926","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["NETWORKS-024.002.003","NETWORKS-024.002.003","NETWORKS-024.002.003"],"award-info":[{"award-number":["NETWORKS-024.002.003","NETWORKS-024.002.003","NETWORKS-024.002.003"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,10]]},"abstract":"Abstract<\/jats:title>An elastic-degenerate (ED) string is a sequence of n<\/jats:italic> finite sets of strings of total length N<\/jats:italic>, introduced to represent a set of related DNA sequences, also known as a pangenome<\/jats:italic>. The ED string matching (EDSM) problem consists in reporting all occurrences of a pattern of length m<\/jats:italic> in an ED text. The EDSM problem has recently received some attention by the combinatorial pattern matching community, culminating in an $$\\mathcal {\\tilde{O}}(nm^{\\omega -1})+\\mathcal {O}(N)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n \n (<\/mml:mo>\n n<\/mml:mi>\n \n m<\/mml:mi>\n \n \u03c9<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n O<\/mml:mi>\n \n (<\/mml:mo>\n N<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-time algorithm [Bernardini et al., SIAM J. Comput. 2022], where $$\\omega $$<\/jats:tex-math>\n \u03c9<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> denotes the matrix multiplication exponent and the $$\\mathcal {\\tilde{O}}(\\cdot )$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n \n (<\/mml:mo>\n \u00b7<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> notation suppresses polylog factors. In the k<\/jats:italic>-EDSM problem, the approximate version of EDSM, we are asked to report all pattern occurrences with at most k<\/jats:italic> errors. k<\/jats:italic>-EDSM can be solved in $$\\mathcal {O}(k^2mG+kN)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n k<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n m<\/mml:mi>\n G<\/mml:mi>\n +<\/mml:mo>\n k<\/mml:mi>\n N<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time, under edit distance, or $$\\mathcal {O}(kmG+kN)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n k<\/mml:mi>\n m<\/mml:mi>\n G<\/mml:mi>\n +<\/mml:mo>\n k<\/mml:mi>\n N<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time, under Hamming distance, where G<\/jats:italic> denotes the total number of strings in the ED text [Bernardini et al., Theor. Comput. Sci. 2020]. Unfortunately, G<\/jats:italic> is only bounded by N<\/jats:italic>, and so even for $$k=1$$<\/jats:tex-math>\n \n k<\/mml:mi>\n =<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the existing algorithms run in $$\\varOmega (mN)$$<\/jats:tex-math>\n \n \u03a9<\/mml:mi>\n (<\/mml:mo>\n m<\/mml:mi>\n N<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time in the worst case. In this paper we make progress in this direction. We show that 1-EDSM can be solved in $$\\mathcal {O}((nm^2 + N)\\log m)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n (<\/mml:mo>\n n<\/mml:mi>\n \n m<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n +<\/mml:mo>\n N<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n log<\/mml:mo>\n m<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> or $$\\mathcal {O}(nm^3 + N)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n \n m<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msup>\n +<\/mml:mo>\n N<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time under edit distance. For the decision version of the problem, we present a faster $$\\mathcal {O}(nm^2\\sqrt{\\log m} + N\\log \\log m)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n \n m<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \n \n log<\/mml:mo>\n m<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msqrt>\n +<\/mml:mo>\n N<\/mml:mi>\n log<\/mml:mo>\n log<\/mml:mo>\n m<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-time algorithm. We also show that 1-EDSM can be solved in $$\\mathcal {O}(nm^2 + N\\log m)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n \n m<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n +<\/mml:mo>\n N<\/mml:mi>\n log<\/mml:mo>\n m<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time under Hamming distance. Our algorithms for edit distance rely on non-trivial reductions from 1-EDSM to special instances of classic computational geometry problems (2d rectangle stabbing or 2d range emptiness), which we show how to solve efficiently. In order to obtain an even faster algorithm for Hamming distance, we rely on employing and adapting the k<\/jats:italic>-errata trees for indexing with errors [Cole et al., STOC 2004]. This is an extended version of a paper presented at LATIN 2022.<\/jats:p>","DOI":"10.1007\/s00224-024-10194-8","type":"journal-article","created":{"date-parts":[[2024,9,16]],"date-time":"2024-09-16T02:01:57Z","timestamp":1726452117000},"page":"1442-1467","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Elastic-Degenerate String Matching with 1 Error or Mismatch"],"prefix":"10.1007","volume":"68","author":[{"given":"Giulia","family":"Bernardini","sequence":"first","affiliation":[]},{"given":"Esteban","family":"Gabory","sequence":"additional","affiliation":[]},{"given":"Solon P.","family":"Pissis","sequence":"additional","affiliation":[]},{"given":"Leen","family":"Stougie","sequence":"additional","affiliation":[]},{"given":"Michelle","family":"Sweering","sequence":"additional","affiliation":[]},{"given":"Wiktor","family":"Zuba","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,9,16]]},"reference":[{"key":"10194_CR1","doi-asserted-by":"publisher","unstructured":"Akutsu, T.: A linear time pattern matching algorithm between a string and a tree. In: Apostolico, A., Crochemore, M., Galil, Z., Manber, U. (eds.) Combinatorial Pattern Matching, 4th Annual Symposium, CPM 93, Padova, Italy, June 2-4, 1993, Proceedings, Lecture Notes in Computer Science, vol. 684, pp. 1\u201310. Springer (1993). https:\/\/doi.org\/10.1007\/BFb0029792","DOI":"10.1007\/BFb0029792"},{"key":"10194_CR2","doi-asserted-by":"publisher","unstructured":"Alzamel, M., Ayad, L.A.K., Bernardini, G., Grossi, R., Iliopoulos, C.S., Pisanti, N., Pissis, S.P., Rosone, G.: Degenerate string comparison and applications. In: Parida, L., Ukkonen, E. (eds.) 18th International Workshop on Algorithms in Bioinformatics, WABI 2018, August 20-22, 2018, Helsinki, Finland, LIPIcs, vol. 113, pp. 21:1\u201321:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.WABI.2018.21","DOI":"10.4230\/LIPIcs.WABI.2018.21"},{"issue":"1\u20134","key":"10194_CR3","doi-asserted-by":"publisher","first-page":"41","DOI":"10.3233\/FI-2020-1947","volume":"175","author":"M Alzamel","year":"2020","unstructured":"Alzamel, M., Ayad, L.A.K., Bernardini, G., Grossi, R., Iliopoulos, C.S., Pisanti, N., Pissis, S.P., Rosone, G.: Comparing degenerate strings. Fundam. Informaticae 175(1\u20134), 41\u201358 (2020). https:\/\/doi.org\/10.3233\/FI-2020-1947","journal-title":"Comparing degenerate strings. Fundam. Informaticae"},{"issue":"2","key":"10194_CR4","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1006\/jagm.2000.1104","volume":"37","author":"A Amir","year":"2000","unstructured":"Amir, A., Keselman, D., Landau, G.M., Lewenstein, M., Lewenstein, N., Rodeh, M.: Text indexing and dictionary matching with one error. J. Algorithms 37(2), 309\u2013325 (2000). https:\/\/doi.org\/10.1006\/jagm.2000.1104","journal-title":"J. Algorithms"},{"issue":"1","key":"10194_CR5","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1006\/jagm.1999.1063","volume":"35","author":"A Amir","year":"2000","unstructured":"Amir, A., Lewenstein, M., Lewenstein, N.: Pattern matching in hypertext. J. Algorithms 35(1), 82\u201399 (2000). https:\/\/doi.org\/10.1006\/jagm.1999.1063","journal-title":"J. Algorithms"},{"issue":"2","key":"10194_CR6","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0196-6774(03)00097-X","volume":"50","author":"A Amir","year":"2004","unstructured":"Amir, A., Lewenstein, M., Porat, E.: Faster algorithms for string matching with k mismatches. J. Algorithms 50(2), 257\u2013275 (2004). https:\/\/doi.org\/10.1016\/S0196-6774(03)00097-X","journal-title":"J. Algorithms"},{"key":"10194_CR7","doi-asserted-by":"publisher","unstructured":"Aoyama, K., Nakashima, Y., I, T., Inenaga, S., Bannai, H., Takeda, M.: Faster online elastic degenerate string matching. In: Navarro, G., Sankoff, D., Zhu, B. (eds.) Annual Symposium on Combinatorial Pattern Matching, CPM 2018, July 2-4, 2018 - Qingdao, China, LIPIcs, vol. 105, pp. 9:1\u20139:10. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2018.9","DOI":"10.4230\/LIPIcs.CPM.2018.9"},{"key":"10194_CR8","doi-asserted-by":"publisher","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Panario, D., Viola, A. (eds.) LATIN 2000: Theoretical Informatics, 4th Latin American Symposium, Punta del Este, Uruguay, April 10-14, 2000, Proceedings, Lecture Notes in Computer Science, vol. 1776, pp. 88\u201394. Springer (2000). https:\/\/doi.org\/10.1007\/10719839_9","DOI":"10.1007\/10719839_9"},{"key":"10194_CR9","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/978-3-031-20624-5_2","volume-title":"LATIN 2022: Theoretical Informatics","author":"G Bernardini","year":"2022","unstructured":"Bernardini, G., Gabory, E., Pissis, S.P., Stougie, L., Sweering, M., Zuba, W.: Elastic-degenerate string matching with 1 error. In: Casta\u00f1eda, A., Rodr\u00edguez-Henr\u00edquez, F. (eds.) LATIN 2022: Theoretical Informatics, pp. 20\u201337. Springer International Publishing, Cham (2022)"},{"key":"10194_CR10","doi-asserted-by":"publisher","unstructured":"Bernardini, G., Gawrychowski, P., Pisanti, N., Pissis, S.P., Rosone, G.: Even faster elastic-degenerate string matching via fast matrix multiplication. In: Baier, C., Chatzigiannakis, I., Flocchini, P., Leonardi, S. (eds.) 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, LIPIcs, vol. 132, pp. 21:1\u201321:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.21","DOI":"10.4230\/LIPIcs.ICALP.2019.21"},{"issue":"3","key":"10194_CR11","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1137\/20M1368033","volume":"51","author":"G Bernardini","year":"2022","unstructured":"Bernardini, G., Gawrychowski, P., Pisanti, N., Pissis, S.P., Rosone, G.: Elastic-degenerate string matching via fast matrix multiplication. SIAM J. Comput. 51(3), 549\u2013576 (2022). https:\/\/doi.org\/10.1137\/20M1368033","journal-title":"SIAM J. Comput."},{"key":"10194_CR12","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.tcs.2019.08.012","volume":"812","author":"G Bernardini","year":"2020","unstructured":"Bernardini, G., Pisanti, N., Pissis, S.P., Rosone, G.: Approximate pattern matching on elastic-degenerate text. Theor. Comput. Sci. 812, 109\u2013122 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"10194_CR13","doi-asserted-by":"publisher","unstructured":"Carletti, V., Foggia, P., Garrison, E., Greco, L., Ritrovato, P., Vento, M.: Graph-based representations for supporting genome data analysis and visualization: Opportunities and challenges. In: Conte, D., Ramel, J., Foggia, P. (eds.) Graph-Based Representations in Pattern Recognition - 12th IAPR-TC-15 International Workshop, GbRPR 2019, Tours, France, June 19-21, 2019, Proceedings, Lecture Notes in Computer Science, vol. 11510, pp. 237\u2013246. Springer (2019). https:\/\/doi.org\/10.1007\/978-3-030-20081-7_23","DOI":"10.1007\/978-3-030-20081-7_23"},{"key":"10194_CR14","doi-asserted-by":"publisher","unstructured":"Chan, T.M., Larsen, K.G., Patrascu, M.: Orthogonal range searching on the RAM, revisited. In: Hurtado, F., van Kreveld, M.J., (eds.) Proceedings of the 27th ACM Symposium on Computational Geometry, Paris, France, June 13-15, 2011, pp. 1\u201310. ACM (2011). https:\/\/doi.org\/10.1145\/1998196.1998198","DOI":"10.1145\/1998196.1998198"},{"key":"10194_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3385898","volume":"25","author":"P Charalampopoulos","year":"2020","unstructured":"Charalampopoulos, P., Iliopoulos, C.S., Liu, C., Pissis, S.P.: Property suffix array with applications in indexing weighted sequences. ACM J. Exp. Algorithmics 25, 1\u201316 (2020). https:\/\/doi.org\/10.1145\/3385898","journal-title":"ACM J. Exp. Algorithmics"},{"key":"10194_CR16","doi-asserted-by":"publisher","unstructured":"Charalampopoulos, P., Kociumaka, T., Wellnitz, P.: Faster approximate pattern matching: A unified approach. In: Irani, S. (ed.) 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pp. 978\u2013989. IEEE (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00095","DOI":"10.1109\/FOCS46700.2020.00095"},{"key":"10194_CR17","doi-asserted-by":"publisher","unstructured":"Charalampopoulos, P., Kociumaka, T., Wellnitz, P.: 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, Denver, CO, USA, October 31 - November 3, 2022, pp. 698\u2013707. IEEE (2022). https:\/\/doi.org\/10.1109\/FOCS54457.2022.00072","DOI":"10.1109\/FOCS54457.2022.00072"},{"issue":"3","key":"10194_CR18","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1137\/0217026","volume":"17","author":"B Chazelle","year":"1988","unstructured":"Chazelle, B.: A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput. 17(3), 427\u2013462 (1988). https:\/\/doi.org\/10.1137\/0217026","journal-title":"SIAM J. Comput."},{"issue":"24","key":"10194_CR19","doi-asserted-by":"publisher","first-page":"4290","DOI":"10.1093\/bioinformatics\/bty506","volume":"34","author":"A Cislak","year":"2018","unstructured":"Cislak, A., Grabowski, S., Holub, J.: SOPanG: online text searching over a pan-genome. Bioinform. 34(24), 4290\u20134292 (2018). https:\/\/doi.org\/10.1093\/bioinformatics\/bty506","journal-title":"Bioinform."},{"key":"10194_CR20","doi-asserted-by":"publisher","unstructured":"Cole, R., Gottlieb, L., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: Babai, L. (ed.) Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pp. 91\u2013100. ACM (2004). https:\/\/doi.org\/10.1145\/1007352.1007374","DOI":"10.1145\/1007352.1007374"},{"issue":"6","key":"10194_CR21","doi-asserted-by":"publisher","first-page":"1761","DOI":"10.1137\/S0097539700370527","volume":"31","author":"R Cole","year":"2002","unstructured":"Cole, R., Hariharan, R.: Approximate string matching: A simpler faster algorithm. SIAM J. Comput. 31(6), 1761\u20131782 (2002). https:\/\/doi.org\/10.1137\/S0097539700370527","journal-title":"SIAM J. Comput."},{"key":"10194_CR22","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on strings. Cambridge University Press (2007)","DOI":"10.1017\/CBO9780511546853"},{"key":"10194_CR23","doi-asserted-by":"publisher","unstructured":"Equi, M., M\u00e4kinen, V., Tomescu, A.I., Grossi, R.: On the complexity of string matching for graphs. ACM Trans. Algorithms 19(3), 21:1\u201321:25 (2023). https:\/\/doi.org\/10.1145\/3588334","DOI":"10.1145\/3588334"},{"key":"10194_CR24","doi-asserted-by":"publisher","unstructured":"Equi, M., Norri, T., Alanko, J., Cazaux, B., Tomescu, A.I., M\u00e4kinen, V.: Algorithms and complexity on indexing elastic founder graphs. In: Ahn, H., Sadakane, K. (eds.) 32nd International Symposium on Algorithms and Computation, ISAAC 2021, December 6-8, 2021, Fukuoka, Japan, LIPIcs, vol. 212, pp. 20:1\u201320:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2021.20","DOI":"10.4230\/LIPIcs.ISAAC.2021.20"},{"key":"10194_CR25","doi-asserted-by":"publisher","unstructured":"Farach, M.: Optimal suffix tree construction with large alphabets. In: 38th Annual Symposium On Foundations Of Computer Science, FOCS \u201997, Miami Beach, Florida, USA, October 19-22, 1997, pp. 137\u2013143. IEEE Computer Society (1997). https:\/\/doi.org\/10.1109\/SFCS.1997.646102","DOI":"10.1109\/SFCS.1997.646102"},{"issue":"3","key":"10194_CR26","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"ML Fredman","year":"1984","unstructured":"Fredman, M.L., Koml\u00f3s, J., Szemer\u00e9di, E.: Storing a sparse table with 0(1) worst case access time. J. ACM 31(3), 538\u2013544 (1984). https:\/\/doi.org\/10.1145\/828.1884","journal-title":"J. ACM"},{"key":"10194_CR27","doi-asserted-by":"publisher","unstructured":"Gao, Y., He, M., Nekrich, Y.: Fast preprocessing for optimal orthogonal range reporting and range successor with applications to text indexing. In: Grandoni, F., Herman, G., Sanders, P. (eds.) 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), LIPIcs, vol. 173, pp. 54:1\u201354:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2020.54","DOI":"10.4230\/LIPIcs.ESA.2020.54"},{"key":"10194_CR28","doi-asserted-by":"publisher","unstructured":"Gawrychowski, P., Ghazawi, S., Landau, G.M.: On indeterminate strings matching. In: G\u00f8rtz, I.L., Weimann, O. (eds.) 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, June 17-19, 2020, Copenhagen, Denmark, LIPIcs, vol. 161, pp. 14:1\u201314:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2020.14","DOI":"10.4230\/LIPIcs.CPM.2020.14"},{"key":"10194_CR29","doi-asserted-by":"publisher","unstructured":"Gawrychowski, P., Uznanski, P.: Towards unified approximate pattern matching for Hamming and l_1 distance. In: Chatzigiannakis, I., Kaklamanis, C., Marx, D., Sannella, D. (eds.) 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, LIPIcs, vol. 107, pp. 62:1\u201362:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.62","DOI":"10.4230\/LIPIcs.ICALP.2018.62"},{"key":"10194_CR30","doi-asserted-by":"publisher","unstructured":"Gibney, D.: An efficient elastic-degenerate text index? not likely. In: Boucher, C., Thankachan, S.V. (eds.) String Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, Orlando, FL, USA, October 13-15, 2020, Proceedings, Lecture Notes in Computer Science, vol. 12303, pp. 76\u201388. Springer (2020). https:\/\/doi.org\/10.1007\/978-3-030-59212-7_6","DOI":"10.1007\/978-3-030-59212-7_6"},{"key":"10194_CR31","doi-asserted-by":"publisher","unstructured":"Grossi, R., Iliopoulos, C.S., Liu, C., Pisanti, N., Pissis, S.P., Retha, A., Rosone, G., Vayani, F., Versari, L.: On-line pattern matching on similar texts. In: K\u00e4rkk\u00e4inen, J., Radoszewski, J., Rytter, W. (eds.) 28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017, July 4-6, 2017, Warsaw, Poland, LIPIcs, vol.\u00a078, pp. 9:1\u20139:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2017.9","DOI":"10.4230\/LIPIcs.CPM.2017.9"},{"key":"10194_CR32","doi-asserted-by":"publisher","unstructured":"Iliopoulos, C.S., Kundu, R., Pissis, S.P.: Efficient pattern matching in elastic-degenerate strings. Inf. Comput. 279, 104,616 (2021). https:\/\/doi.org\/10.1016\/j.ic.2020.104616","DOI":"10.1016\/j.ic.2020.104616"},{"issue":"20","key":"10194_CR33","doi-asserted-by":"publisher","first-page":"4022","DOI":"10.1016\/0022-2836(71)90319-6","volume":"9","author":"IUPAC-IUB Commission on Biochemical Nomenclature","year":"1970","unstructured":"IUPAC-IUB Commission on Biochemical Nomenclature: Abbreviations and symbols for nucleic acids, polynucleotides, and their constituents. Biochemistry 9(20), 4022\u20134027 (1970). https:\/\/doi.org\/10.1016\/0022-2836(71)90319-6","journal-title":"Biochemistry"},{"key":"10194_CR34","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0304-3975(86)90178-7","volume":"43","author":"GM Landau","year":"1986","unstructured":"Landau, G.M., Vishkin, U.: Efficient string matching with k mismatches. Theor. Comput. Sci. 43, 239\u2013249 (1986). https:\/\/doi.org\/10.1016\/0304-3975(86)90178-7","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"10194_CR35","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0022-0000(88)90045-1","volume":"37","author":"GM Landau","year":"1988","unstructured":"Landau, G.M., Vishkin, U.: Fast string matching with k differences. J. Comput. Syst. Sci. 37(1), 63\u201378 (1988). https:\/\/doi.org\/10.1016\/0022-0000(88)90045-1","journal-title":"J. Comput. Syst. Sci."},{"key":"10194_CR36","doi-asserted-by":"publisher","unstructured":"M\u00e4kinen, V., Cazaux, B., Equi, M., Norri, T., Tomescu, A.I.: Linear time construction of indexable founder block graphs. In: Kingsford, C., Pisanti, N. (eds.) 20th International Workshop on Algorithms in Bioinformatics, WABI 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), LIPIcs, vol. 172, pp. 7:1\u20137:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.WABI.2020.7","DOI":"10.4230\/LIPIcs.WABI.2020.7"},{"key":"10194_CR37","doi-asserted-by":"publisher","unstructured":"Manber, U., Wu, S.: Approximate string matching with arbitrary costs for text and hypertext, pp. 22\u201333. https:\/\/doi.org\/10.1142\/9789812797919_0002. https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/9789812797919_0002","DOI":"10.1142\/9789812797919_0002"},{"key":"10194_CR38","doi-asserted-by":"crossref","unstructured":"Na, J.C., Apostolico, A., Iliopoulos, C.S., Park, K.: Truncated suffix trees and their application to data compression. Theor. Comput. Sci. 304(1-3), 87\u2013101 (2003). https:\/\/doi.org\/10.1016\/S0304-3975(03)00053-7","DOI":"10.1016\/S0304-3975(03)00053-7"},{"issue":"1\u20132","key":"10194_CR39","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1016\/S0304-3975(99)00333-3","volume":"237","author":"G Navarro","year":"2000","unstructured":"Navarro, G.: Improved approximate pattern matching on hypertext. Theor. Comput. Sci. 237(1\u20132), 455\u2013463 (2000). https:\/\/doi.org\/10.1016\/S0304-3975(99)00333-3","journal-title":"Theor. Comput. Sci."},{"key":"10194_CR40","doi-asserted-by":"publisher","unstructured":"Park, K., Kim, D.K.: String matching in hypertext. In: Galil, Z., Ukkonen, E., (eds.) Combinatorial Pattern Matching, 6th Annual Symposium, CPM 95, Espoo, Finland, July 5-7, 1995, Proceedings, Lecture Notes in Computer Science, vol. 937, pp. 318\u2013329. Springer (1995). https:\/\/doi.org\/10.1007\/3-540-60044-2_51","DOI":"10.1007\/3-540-60044-2_51"},{"key":"10194_CR41","doi-asserted-by":"publisher","unstructured":"Pissis, S.P., Retha, A.: Dictionary matching in elastic-degenerate texts with applications in searching VCF files on-line. In: D\u2019Angelo, G. (ed.) 17th International Symposium on Experimental Algorithms, SEA 2018, June 27-29, 2018, L\u2019Aquila, Italy, LIPIcs, vol. 103, pp. 16:1\u201316:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.SEA.2018.16","DOI":"10.4230\/LIPIcs.SEA.2018.16"},{"issue":"19","key":"10194_CR42","doi-asserted-by":"publisher","first-page":"3599","DOI":"10.1093\/bioinformatics\/btz162","volume":"35","author":"M Rautiainen","year":"2019","unstructured":"Rautiainen, M., M\u00e4kinen, V., Marschall, T.: Bit-parallel sequence-to-graph alignment. Bioinform. 35(19), 3599\u20133607 (2019). https:\/\/doi.org\/10.1093\/bioinformatics\/btz162","journal-title":"Bit-parallel sequence-to-graph alignment. Bioinform."},{"key":"10194_CR43","doi-asserted-by":"publisher","unstructured":"Ruzic, M.: Constructing efficient dictionaries in close to sorting time. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games, Lecture Notes in Computer Science, vol. 5125, pp. 84\u201395. Springer (2008). https:\/\/doi.org\/10.1007\/978-3-540-70575-8_8","DOI":"10.1007\/978-3-540-70575-8_8"},{"issue":"6","key":"10194_CR44","doi-asserted-by":"publisher","first-page":"1474","DOI":"10.1137\/S0097539703435728","volume":"34","author":"Q Shi","year":"2005","unstructured":"Shi, Q., J\u00e1J\u00e1, J.F.: Novel transformation techniques using q-heaps with applications to computational geometry. SIAM J. Comput. 34(6), 1474\u20131492 (2005). https:\/\/doi.org\/10.1137\/S0097539703435728","journal-title":"SIAM J. Comput."},{"key":"10194_CR45","doi-asserted-by":"publisher","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983). https:\/\/doi.org\/10.1016\/0022-0000(83)90006-5. https:\/\/www.sciencedirect.com\/science\/article\/pii\/0022000083900065","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"10194_CR46","doi-asserted-by":"publisher","unstructured":"Thankachan, S.V., Apostolico, A., Aluru, S.: A provably efficient algorithm for the k-mismatch average common substring problem. J. Comput. Biol. 23(6), 472\u2013482 (2016). https:\/\/doi.org\/10.1089\/cmb.2015.0235. http:\/\/www.liebertpub.com\/doi\/10.1089\/cmb.2015.0235","DOI":"10.1089\/cmb.2015.0235"},{"issue":"1","key":"10194_CR47","first-page":"118","volume":"19","author":"The Computational Pan-Genomics Consortium","year":"2018","unstructured":"The Computational Pan-Genomics Consortium: Computational pan-genomics: status, promises and challenges. Briefings Bioinforma 19(1), 118\u2013135 (2018)","journal-title":"Briefings Bioinforma"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10194-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10194-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10194-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T09:55:53Z","timestamp":1729850153000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10194-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,16]]},"references-count":47,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["10194"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10194-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2024,9,16]]},"assertion":[{"value":"6 August 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 September 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}