{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:12:32Z","timestamp":1760202752462,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2018,11,13]],"date-time":"2018-11-13T00:00:00Z","timestamp":1542067200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,6]]},"DOI":"10.1007\/s00453-018-0526-2","type":"journal-article","created":{"date-parts":[[2018,11,13]],"date-time":"2018-11-13T06:17:37Z","timestamp":1542089857000},"page":"2123-2157","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Mind the Gap!"],"prefix":"10.1007","volume":"81","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[]},{"given":"Tsvi","family":"Kopelowitz","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1686-0094","authenticated-orcid":false,"given":"Avivit","family":"Levy","sequence":"additional","affiliation":[]},{"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[]},{"given":"Ely","family":"Porat","sequence":"additional","affiliation":[]},{"given":"B. Riva","family":"Shalom","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,11,13]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Abboud, A., Williams, V.V.: Popular conjectures imply strong lower bounds for dynamic problems. In: Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (2014)","key":"526_CR1","DOI":"10.1109\/FOCS.2014.53"},{"issue":"6","key":"526_CR2","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"VA Alfred","year":"1975","unstructured":"Alfred, V.A., Corasick, J.C.: Efficient string matching: an aid to bibliographic search. Commun. ACM 18(6), 333\u2013340 (1975)","journal-title":"Commun. ACM"},{"issue":"4","key":"526_CR3","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. Assoc. Comput. Mach. (JACM) 42(4), 844\u2013856 (1995)","journal-title":"J. Assoc. Comput. Mach. (JACM)"},{"issue":"2","key":"526_CR4","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1006\/inco.1995.1090","volume":"119","author":"A Amir","year":"1995","unstructured":"Amir, A., Farach, M., Idury, R.M., La Poutr\u00e9, J.A., Sch\u00e4ffer, A.A.: Improved dynamic dictionary matching. Inf. Comput. 119(2), 258\u2013282 (1995)","journal-title":"Inf. Comput."},{"issue":"2","key":"526_CR5","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)","journal-title":"J. Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Amir, A., Levy, A., Porat, E., Shalom, B.R.: Dictionary matching with one gap. In: Proceedings of the 25th Annual Symposium on Combinatorial Pattern Matching (CPM), pp.\u00a011\u201320 (2014)","key":"526_CR6","DOI":"10.1007\/978-3-319-07566-2_2"},{"issue":"1","key":"526_CR7","doi-asserted-by":"publisher","first-page":"69","DOI":"10.4086\/toc.2012.v008a004","volume":"8","author":"N Bansal","year":"2012","unstructured":"Bansal, N., Williams, R.: Regularity lemmas and combinatorial algorithms. Theory Comput. 8(1), 69\u201394 (2012)","journal-title":"Theory Comput."},{"key":"526_CR8","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.tcs.2012.03.029","volume":"443","author":"P Bille","year":"2012","unstructured":"Bille, P., G\u00f8rtz, I.L., Vildh\u00f8j, H.W., Wind, D.K.: String matching with variable length gaps. Theor. Comput. Sci. 443, 25\u201334 (2012)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Bille, P., Thorup, M.: Regular expression matching with multi-strings and intervals. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\u00a01297\u20131308 (2010)","key":"526_CR9","DOI":"10.1137\/1.9781611973075.104"},{"doi-asserted-by":"crossref","unstructured":"Bj\u00f8rklund, A., Pagh, R., Williams, V.V., Zwick, U.: Listing triangles. In: Proceedings of of 41st International Colloquium on Automata, Languages, and Programming (ICALP (I)), pp.\u00a0223\u2013234 (2014)","key":"526_CR10","DOI":"10.1007\/978-3-662-43948-7_19"},{"doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Gasieniec, L.: Approximate dictionary queries. In: Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching (CPM), pp.\u00a065\u201374 (1996)","key":"526_CR11","DOI":"10.1007\/3-540-61258-0_6"},{"issue":"1","key":"526_CR12","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/0214017","volume":"14","author":"N Chiba","year":"1985","unstructured":"Chiba, N., Nishizeki, T.: Arboricity and subgraph listing algorithms. SIAM J. Comput. (SICOMP) 14(1), 210\u2013223 (1985)","journal-title":"SIAM J. Comput. (SICOMP)"},{"issue":"40\u201342","key":"526_CR13","doi-asserted-by":"publisher","first-page":"3795","DOI":"10.1016\/j.tcs.2010.06.002","volume":"411","author":"H Cohen","year":"2010","unstructured":"Cohen, H., Porat, E.: Fast set intersection and two-patterns matching. Theor. Comput. Sci. 411(40\u201342), 3795\u20133800 (2010)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.-A., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: Proceedings of the 36 Annual Symposium on Theory of Computing (STOC), pp.\u00a091\u2013100 (2004)","key":"526_CR14","DOI":"10.1145\/1007352.1007374"},{"doi-asserted-by":"crossref","unstructured":"de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry, 2 reised edn, ch. Section 10.1: Interval Trees (ed.), p. 212217. Springer, Berlin (2000)","key":"526_CR15","DOI":"10.1007\/978-3-662-04245-8_1"},{"issue":"4","key":"526_CR16","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/s10791-008-9054-z","volume":"11","author":"K Fredriksson","year":"2008","unstructured":"Fredriksson, K., Grabowski, S.: Efficient algorithms for pattern matching with general gaps, character classes, and transposition invariance. Inf. Retr. 11(4), 335\u2013357 (2008)","journal-title":"Inf. Retr."},{"doi-asserted-by":"crossref","unstructured":"Gr\u00f8nlund, A., Pettie, S.: Threesomes, degenerates, and love triangles. In: Proceedings of 55th IEEE Anuual Symposium on Foundation of Computer Science (FOCS), pp.\u00a0621\u2013630 (2014)","key":"526_CR17","DOI":"10.1109\/FOCS.2014.72"},{"doi-asserted-by":"crossref","unstructured":"Haapasalo, T., Silvasti, P., Sippu, S., Soisalon-Soininen, E.: Online dictionary matching with variable-length gaps. In: Proceedings of International Symposium on Experimental Algorithms (SEA), pp.\u00a076\u201387 (2011)","key":"526_CR18","DOI":"10.1007\/978-3-642-20662-7_7"},{"doi-asserted-by":"crossref","unstructured":"Henzinger, M., Krinninger, S., Nanongkai, D., Saranurak, T.: Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In: Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), pp.\u00a021\u201330 (2015)","key":"526_CR19","DOI":"10.1145\/2746539.2746609"},{"issue":"1","key":"526_CR20","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1093\/nar\/27.1.215","volume":"27","author":"K Hofmann","year":"1999","unstructured":"Hofmann, K., Bucher, P., Falquet, L., Bairoch, A.: The PROSITE database, its status in 1999. Nucl. Acids Res. 27(1), 215\u2013219 (1999)","journal-title":"Nucl. Acids Res."},{"doi-asserted-by":"crossref","unstructured":"Hon, W.-K., Lam, T.-W., Shah, R., Thankachan, S.V., Ting, H.-F., Yang, Y.: Dictionary matching with uneven gaps. In: Proceedings of the 26th Annual Symposium on Combinatorial Pattern Matching (CPM), pp.\u00a0247\u2013260 (2015)","key":"526_CR21","DOI":"10.1007\/978-3-319-19929-0_21"},{"issue":"4","key":"526_CR22","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0207033","volume":"7","author":"A Itai","year":"1978","unstructured":"Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. SIAM J. Comput. (SICOMP) 7(4), 413\u2013423 (1978)","journal-title":"SIAM J. Comput. (SICOMP)"},{"doi-asserted-by":"crossref","unstructured":"Kopelowitz, T., Pettie, S., Porat, E.: Dynamic set intersection. In: Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS) (2015)","key":"526_CR23","DOI":"10.1007\/978-3-319-21840-3_39"},{"doi-asserted-by":"crossref","unstructured":"Kopelowitz, T., Pettie, S., Porat, E.: Higher lower bounds from the 3-sum conjecture. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2016)","key":"526_CR24","DOI":"10.1137\/1.9781611974331.ch89"},{"issue":"1\u20132","key":"526_CR25","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0304-3975(97)88195-9","volume":"178","author":"G Kucherov","year":"1997","unstructured":"Kucherov, G., Rusinowitch, M.: Matching a set of strings with variable length don\u2019t cares. Theor. Comput. Sci. 178(1\u20132), 129\u2013154 (1997)","journal-title":"Theor. Comput. Sci."},{"issue":"8","key":"526_CR26","doi-asserted-by":"publisher","first-page":"1065","DOI":"10.1089\/cmb.2005.12.1065","volume":"12","author":"M Morgante","year":"2005","unstructured":"Morgante, M., Policriti, A., Vitacolonna, N., Zuccolo, A.: Structured motifs search. J. Comput. Biol. 12(8), 1065\u20131082 (2005)","journal-title":"J. Comput. Biol."},{"issue":"6","key":"526_CR27","doi-asserted-by":"publisher","first-page":"1494","DOI":"10.1137\/S0097539703436722","volume":"35","author":"CW Mortensen","year":"2006","unstructured":"Mortensen, C.W.: Fully dynamic orthogonal range reporting on RAM. SIAM J. Comput. 35(6), 1494\u20131525 (2006)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"526_CR28","first-page":"430","volume":"39","author":"W Eugene","year":"1992","unstructured":"Eugene, W., Myers, G.: A four russians algorithm for regular expression pattern matching. J. ACM 39(2), 430\u2013448 (1992)","journal-title":"J. ACM"},{"issue":"3","key":"526_CR29","first-page":"299","volume":"9","author":"G Myers","year":"1993","unstructured":"Myers, G., Mehldau, G.: A system for pattern matching applications on biosequences. CABIOS 9(3), 299\u2013314 (1993)","journal-title":"CABIOS"},{"issue":"6","key":"526_CR30","doi-asserted-by":"publisher","first-page":"903","DOI":"10.1089\/106652703322756140","volume":"10","author":"G Navarro","year":"2003","unstructured":"Navarro, G., Raffinot, M.: Fast and simple character classes and bounded gaps pattern matching, with applications to protein searching. J. Comput. Biol. 10(6), 903\u2013923 (2003)","journal-title":"J. Comput. Biol."},{"doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M.: Towards polynomial lower bounds for dynamic problems. In: Proceedings of 42nd ACM Symposium on Theory of Computing (STOC), pp.\u00a0603\u2013610 (2010)","key":"526_CR31","DOI":"10.1145\/1806689.1806772"},{"unstructured":"VerInt.: Personal communication (2013)","key":"526_CR32"},{"issue":"6","key":"526_CR33","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/j.ipl.2009.12.007","volume":"110","author":"M Zhang","year":"2010","unstructured":"Zhang, M., Zhang, Y., Liang, H.: A faster algorithm for matching a set of patterns with variable length don\u2019t cares. Inf. Process. Lett. 110(6), 216\u2013220 (2010)","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0526-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0526-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0526-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,12,16]],"date-time":"2019-12-16T13:04:16Z","timestamp":1576501456000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0526-2"}},"subtitle":["Online Dictionary Matching with One Gap"],"short-title":[],"issued":{"date-parts":[[2018,11,13]]},"references-count":33,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["526"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0526-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,11,13]]},"assertion":[{"value":"15 November 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 November 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 November 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}