{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,28]],"date-time":"2026-07-28T08:32:40Z","timestamp":1785227560491,"version":"3.55.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,2,8]],"date-time":"2017-02-08T00:00:00Z","timestamp":1486512000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,2,8]],"date-time":"2017-02-08T00:00:00Z","timestamp":1486512000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1218904"],"award-info":[{"award-number":["CCF-1218904"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology, Taiwan","doi-asserted-by":"publisher","award":["102-2221-E-007-068"],"award-info":[{"award-number":["102-2221-E-007-068"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007156","name":"Innovation and Technology Commission - Hong Kong","doi-asserted-by":"publisher","award":["ITF 260900235"],"award-info":[{"award-number":["ITF 260900235"]}],"id":[{"id":"10.13039\/501100007156","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1007\/s00453-017-0288-2","type":"journal-article","created":{"date-parts":[[2017,2,8]],"date-time":"2017-02-08T15:12:04Z","timestamp":1486566724000},"page":"698-713","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Dictionary Matching with a Bounded Gap in Pattern or in Text"],"prefix":"10.1007","volume":"80","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0570-2904","authenticated-orcid":false,"given":"Wing-Kai","family":"Hon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tak-Wah","family":"Lam","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rahul","family":"Shah","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sharma V.","family":"Thankachan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hing-Fung","family":"Ting","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yilin","family":"Yang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,2,8]]},"reference":[{"key":"288_CR1","doi-asserted-by":"crossref","unstructured":"Afshani, P., Arge, L., Larsen, K.G.: Higher-dimensional orthogonal range reporting and rectangle stabbing in the pointer machine model. In: Proceedings of ACM Symposuim on Computational Geometry (SoCG), pp. 323\u2013332 (2012)","DOI":"10.1145\/2261250.2261299"},{"issue":"6","key":"288_CR2","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"AV Aho","year":"1975","unstructured":"Aho, A.V., Corasick, M.J.: Efficient string matching: an aid to bibliographic search. Commun. ACM 18(6), 333\u2013340 (1975)","journal-title":"Commun. ACM"},{"key":"288_CR3","doi-asserted-by":"crossref","unstructured":"Amir, A., Farach, M.: Adaptive dictionary matching. In: Proceedings of IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 760\u2013766 (1991)","DOI":"10.1109\/SFCS.1991.185445"},{"issue":"2","key":"288_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., Poutr\u00e9, J.A.L., Sch\u00e4ffer, A.A.: Improved dynamic dictionary matching. Inf. Comput. 119(2), 258\u2013282 (1995)","journal-title":"Inf. Comput."},{"issue":"2","key":"288_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"},{"key":"288_CR6","doi-asserted-by":"crossref","unstructured":"Amir, A., Levy, A., Porat, E., Shalom, B.R.: Dictionary matching with one gap. In: Proceedings of Annual Symposium on Combinatorial Pattern Matching (CPM), pp. 11\u201320 (2014)","DOI":"10.1007\/978-3-319-07566-2_2"},{"key":"288_CR7","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.tcs.2015.04.011","volume":"589","author":"A Amir","year":"2015","unstructured":"Amir, A., Levy, A., Porat, E., Shalom, B.R.: Dictionary matching with a few gaps. Theor. Comput. Sci. 589, 34\u201346 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"288_CR8","doi-asserted-by":"crossref","unstructured":"Belazzougui, D.: Succinct dictionary matching with no slowdown. In: Proceedings of Annual Symposium on Combinatorial Pattern Matching (CPM), pp. 88\u2013100 (2010)","DOI":"10.1007\/978-3-642-13509-5_9"},{"issue":"10","key":"288_CR9","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1145\/359842.359859","volume":"20","author":"RS Boyer","year":"1977","unstructured":"Boyer, R.S., Moore, J.S.: A fast string searching algorithm. Commun. ACM 20(10), 762\u2013772 (1977)","journal-title":"Commun. ACM"},{"key":"288_CR10","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Larsen, K.G., Patrascu, M.: Orthogonal range searching on the RAM, revisited. In: Proceedings of ACM Symposium on Computational Geometry (SoCG), pp. 1\u201310 (2011)","DOI":"10.1145\/1998196.1998198"},{"issue":"3","key":"288_CR11","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1137\/0215051","volume":"15","author":"B Chazelle","year":"1986","unstructured":"Chazelle, B.: Filtering search: a new approach to query-answering. SIAM J. Comput. 15(3), 703\u2013724 (1986)","journal-title":"SIAM J. Comput."},{"key":"288_CR12","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: Proceedings of Annual ACM Symposium on Theory of Computing, pp. 91\u2013100 (2004)","DOI":"10.1145\/1007352.1007374"},{"key":"288_CR13","doi-asserted-by":"crossref","unstructured":"Feigenblat, G., Porat, E., Shiftan, A.: An improved query time for succinct dynamic dictionary matching. In: Proceedings of Annual Symposium on Combinatorial Pattern (CPM), pp. 120\u2013129 (2014)","DOI":"10.1007\/978-3-319-07566-2_13"},{"issue":"4","key":"288_CR14","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P Ferragina","year":"2005","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed text. J. ACM 52(4), 552\u2013581 (2005)","journal-title":"J. ACM"},{"issue":"4","key":"288_CR15","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."},{"issue":"2","key":"288_CR16","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1137\/S0097539702402354","volume":"35","author":"R Grossi","year":"2005","unstructured":"Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J. Comput. 35(2), 378\u2013407 (2005)","journal-title":"SIAM J. Comput."},{"key":"288_CR17","doi-asserted-by":"crossref","unstructured":"Haapasalo, T., Silvasti, P., Sippu, S., Soisalon-Soininen, E.: Online dictionary matching with variable-length gaps. In: Proceedings of Symposium on Experimental Algorithms (SEA), pp. 76\u201387 (2011)","DOI":"10.1007\/978-3-642-20662-7_7"},{"issue":"1","key":"288_CR18","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. Nucleic Acids Res. 27(1), 215\u2013219 (1999)","journal-title":"Nucleic Acids Res."},{"issue":"2","key":"288_CR19","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/s00453-013-9863-3","volume":"72","author":"WK Hon","year":"2015","unstructured":"Hon, W.K., Ku, T.H., Lam, T.W., Shah, R., Tam, S.L., Thankachan, S.V., Vitter, J.S.: Compressing dictionary matching index via sparsification technique. Algorithmica 72(2), 515\u2013538 (2015)","journal-title":"Algorithmica"},{"key":"288_CR20","doi-asserted-by":"crossref","unstructured":"Hon, W.K., Ku, T.H., Shah, R., Thankachan, S.V., Vitter, J.S.: Compressed dictionary matching with one error. In: Proceedings of IEEE Data Compression Conference (DCC), pp. 113\u2013122 (2011)","DOI":"10.1109\/DCC.2011.18"},{"key":"288_CR21","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/j.tcs.2012.10.050","volume":"475","author":"WK Hon","year":"2013","unstructured":"Hon, W.K., Ku, T.H., Shah, R., Thankachan, S.V., Vitter, J.S.: Faster compressed dictionary matching. Theor. Comput. Sci. 475, 113\u2013119 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"288_CR22","doi-asserted-by":"crossref","unstructured":"Hon, W.K., Lam, T.W., Shah, R., Tam, S.L., Vitter, J.S.: Compressed index for dictionary matching. In: Proceedings of IEEE Data Compression Conference (DCC), pp. 23\u201332 (2008)","DOI":"10.1109\/DCC.2008.62"},{"key":"288_CR23","doi-asserted-by":"crossref","unstructured":"Hon, W.K., Lam, T.W., Shah, R., Tam, S.L., Vitter, J.S.: Succinct index for dynamic dictionary matching. In: Proceedings of International Symposium on Algorithms and Computation (ISAAC), pp. 1034\u20131043 (2009)","DOI":"10.1007\/978-3-642-10631-6_104"},{"issue":"2","key":"288_CR24","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"RM Karp","year":"1987","unstructured":"Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM J. Res. Dev. 31(2), 249\u2013260 (1987)","journal-title":"IBM J. Res. Dev."},{"key":"288_CR25","doi-asserted-by":"crossref","unstructured":"Karpinski, M., Nekrich, Y.: Space efficient multi-dimensional range reporting. In: Proceedings of Annual International Conference on Computing and Combinatorics (COCOON), pp. 215\u2013224 (2009)","DOI":"10.1007\/978-3-642-02882-3_22"},{"issue":"2","key":"288_CR26","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth, D.E., Morris Jr., J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"key":"288_CR27","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, 129\u2013154 (1997)","journal-title":"Theor. Comput. Sci."},{"key":"288_CR28","doi-asserted-by":"crossref","unstructured":"Lewenstein, M.: Dictionary matching. In: Encyclopedia of Algorithms, pp. 533\u2013538 (2016)","DOI":"10.1007\/978-1-4939-2864-4_109"},{"issue":"5","key":"288_CR29","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber, U., Myers, E.W.: Suffix arrays: a new method for on-line string searches. SIAM J. Comput. 22(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"288_CR30","first-page":"299","volume":"9","author":"G Mehldau","year":"1993","unstructured":"Mehldau, G., Myers, G.: A system for pattern matching applications on biosequences. Comput. Appl. Biosci. 9(3), 299\u2013314 (1993)","journal-title":"Comput. Appl. Biosci."},{"issue":"6","key":"288_CR31","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."},{"issue":"3","key":"288_CR32","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"DD Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."},{"key":"288_CR33","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: Proceedings of Annual Symposium on Switching and Automata, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"},{"issue":"6","key":"288_CR34","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., Hu, L.: 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\/article\/10.1007\/s00453-017-0288-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0288-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0288-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T04:00:20Z","timestamp":1749960020000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0288-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,8]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["288"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0288-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,2,8]]},"assertion":[{"value":"3 June 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 January 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 February 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}