{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T06:40:04Z","timestamp":1759992004226,"version":"3.37.3"},"reference-count":55,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,7,6]],"date-time":"2021-07-06T00:00:00Z","timestamp":1625529600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,7,6]],"date-time":"2021-07-06T00:00:00Z","timestamp":1625529600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,3]]},"DOI":"10.1007\/s00453-021-00851-6","type":"journal-article","created":{"date-parts":[[2021,7,6]],"date-time":"2021-07-06T03:37:36Z","timestamp":1625542656000},"page":"590-638","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Comparative Study of Dictionary Matching with Gaps: Limitations, Techniques and Challenges"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1686-0094","authenticated-orcid":false,"given":"Avivit","family":"Levy","sequence":"first","affiliation":[]},{"given":"B. Riva","family":"Shalom","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,7,6]]},"reference":[{"key":"851_CR1","unstructured":"Krishnamurthy, M., Seagren, E.S., Alder, R., Bayles, A.W., Burke, J., Carter, S., Faskha, E.: How to Cheat at Securing Linux. Syngress Publishing Inc., Elsevier Inc (2008)"},{"issue":"6","key":"851_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"},{"issue":"1","key":"851_CR3","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1006\/jagm.2000.1081","volume":"36","author":"A Amir","year":"2000","unstructured":"Amir, A., C\u0103linescu, G.: Alphabet-independent and scaled dictionary matching. J. Algorithms 36(1), 34\u201362 (2000)","journal-title":"J. Algorithms"},{"issue":"2","key":"851_CR4","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/S0022-0000(05)80047-9","volume":"49","author":"A Amir","year":"1994","unstructured":"Amir, A., Farach, M., Galil, Z., Giancarlo, R., Park, K.: Dynamic dictionary matching. J. Comput. Syst. Sci. 49(2), 208\u2013222 (1994)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"851_CR5","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":"851_CR6","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":"851_CR7","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Gasieniec, L.: Approximate dictionary queries. In: 7th Annual Symposium on Combinatorial Pattern Matching CPM (Laguna Beach, California, USA), June 10\u201312, pp.\u00a065\u201374 (1996)","DOI":"10.1007\/3-540-61258-0_6"},{"key":"851_CR8","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L., Lewenstein, M., Dictionary matching and indexing with errors and don\u2019t cares. In: Proceedings 36th Annual ACM Symposium on the Theory of Computing (STOC), ACM Press, pp.\u00a091\u2013100 (2004)","DOI":"10.1145\/1007352.1007374"},{"issue":"2","key":"851_CR9","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0304-3975(94)00270-3","volume":"154","author":"RM Idury","year":"1996","unstructured":"Idury, R.M., Sch\u00e4ffer, A.A.: Multiple matching of parameterized patterns. Theor. Comput. Sci. 154(2), 203\u2013224 (1996)","journal-title":"Theor. Comput. Sci."},{"key":"851_CR10","unstructured":"Kleene, S.C.: Representation of events in nerve nets and finite automata"},{"issue":"3","key":"851_CR11","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1016\/j.tcs.2008.08.042","volume":"409","author":"P Bille","year":"2008","unstructured":"Bille, P., Farach-Colton, M.: Fast and compact regular expression matching. Theor. Comput. Sci. 409(3), 486\u2013496 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"851_CR12","doi-asserted-by":"crossref","unstructured":"Bille, P., Thorup, M.: Regular expression matching with multi-strings and intervals. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17\u201319, 2010 (Moses Charikar, ed.), SIAM, pp.\u00a01297\u20131308 (2010)","DOI":"10.1137\/1.9781611973075.104"},{"issue":"2","key":"851_CR13","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1145\/128749.128755","volume":"39","author":"EW Myers","year":"1992","unstructured":"Myers, E.W.: A four russians algorithm for regular expression pattern matching. J. ACM 39(2), 430\u2013448 (1992)","journal-title":"J. ACM"},{"issue":"6","key":"851_CR14","doi-asserted-by":"publisher","first-page":"2123","DOI":"10.1007\/s00453-018-0526-2","volume":"81","author":"A Amir","year":"2019","unstructured":"Amir, A., Kopelowitz, T., Levy, A., Pettie, S., Porat, E., Shalom, B.R.: Mind the gap! online dictionary matching with one gap. Algorithmica 81(6), 2123\u20132157 (2019)","journal-title":"Algorithmica"},{"key":"851_CR15","unstructured":"Amir, A., Kopelowitz, T., Levy, A., Pettie, S., Porat, E., Shalom, B.R.: Mind the gap: essentially optimal algorithms for online dictionary matching with one gap. In: 27th International Symposium on Algorithms and Computation, ISAAC (Sydney, Australia), December 12\u201314, pp.\u00a012:1\u201312:12 (2016)"},{"key":"851_CR16","unstructured":"Amir, A., Levy, A., Porat, E., Shalom, B.R.: Online recognition of dictionary with one gap. In: Proceedings of the Prague Stringology Conference (PSC) (Prague, Czech Republic), August 28\u201330, pp.\u00a03\u201317 (2017)"},{"key":"851_CR17","unstructured":"Verint Systems, Personal communication. 2013, Addres: Maskit St.\u00a033 Herzliya Israel"},{"key":"851_CR18","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."},{"issue":"2","key":"851_CR19","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1515\/popets-2015-0014","volume":"2015","author":"M Chase","year":"2015","unstructured":"Chase, M., Shen, E.: Substring-searchable symmetric encryption. PoPETs 2015(2), 263\u2013281 (2015)","journal-title":"PoPETs"},{"key":"851_CR20","doi-asserted-by":"crossref","unstructured":"Curtmola, R., Garay, J.A., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. ACM CCS 06 (Ari Juels Rebecca\u00a0N. Wright and Sabrina De\u00a0Capitani di\u00a0Vimercati, eds.), ACM Press, pp.\u00a09\u201388 (2006)","DOI":"10.1145\/1180405.1180417"},{"key":"851_CR21","unstructured":"Song, D.X., Wagner, D., Perrig, A.: Practical techniques for searches on encrypted data. In: IEEE Symposium on Security and Privacy IEEE Computer Society Press, pp. 44\u201355 (2000)"},{"key":"851_CR22","doi-asserted-by":"crossref","unstructured":"Boneh, D., Crescenzo, G.D., Ostrovsky, R., Persiano, G.: Public key encryption with keyword search. EUROCRYPT 2004 (Christian Cachin and Jan Camenisch, eds.), LNCS, vol. 3027, Springer, pp.\u00a0506\u2013522 (2004)","DOI":"10.1007\/978-3-540-24676-3_30"},{"key":"851_CR23","doi-asserted-by":"crossref","unstructured":"Desmoulins, N., Fouque, P.A., Onete, C., Sanders, O.: Pattern matching on encrypted streams, ASIACRYPT (2018)","DOI":"10.1007\/978-3-030-03326-2_5"},{"key":"851_CR24","doi-asserted-by":"crossref","unstructured":"Baker, B.S.: A theory of parameterized pattern matching: algorithms and applications. In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing (San Diego, CA, USA), May 16\u201318, pp.\u00a071\u201380 (1993)","DOI":"10.1145\/167088.167115"},{"key":"851_CR25","unstructured":"Shalom, B.R.: Parameterized dictionary matching with one gap. In: Proceedings of the Prague Stringology Conference (PSC) (Prague, Czech Republic), pp.\u00a0103\u2013116 (2018)"},{"key":"851_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2020.11.017","volume":"854","author":"BR Shalom","year":"2021","unstructured":"Shalom, B.R.: Parameterized dictionary matching and recognition with one gap. Theor. Comput. Sci. 854, 1\u201316 (2021)","journal-title":"Theor. Comput. Sci."},{"key":"851_CR27","unstructured":"Levy, A., Shalom, B.R.: Online parameterized dictionary matching with one gap. In: Stringology (Proceedings of the Prague Stringology Conference), pp.\u00a041\u201355 (2019)"},{"key":"851_CR28","doi-asserted-by":"crossref","unstructured":"Levy, A., Shalom, B.R.: Online parameterized dictionary matching with one gap. Submitted for publication (2020)","DOI":"10.1016\/j.tcs.2020.09.016"},{"key":"851_CR29","unstructured":"Burr, S.A., Erd\u0151s, P.: On the magnitude of generalized ramsey numbers for graphs. Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erd\u0151s on his 60th birthday) (J\u00e1nos Bolyai, ed.), Colloq. Math. Soc., vol.\u00a01, 1975, p.\u00a0214\u2013240"},{"issue":"12","key":"851_CR30","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(12), 129\u2013154 (1997)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"851_CR31","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."},{"key":"851_CR32","doi-asserted-by":"crossref","unstructured":"Haapasalo, T., Silvasti, P., Sippu, S., Soisalon-Soininen, E.: Online dictionary matching with variable-length gaps. In: 10th International Symposium on Experimental Algorithms SEA (Kolimpari, Chania, Crete, Greece), May 5\u20137, pp.\u00a076\u201387 (2011)","DOI":"10.1007\/978-3-642-20662-7_7"},{"issue":"2","key":"851_CR33","doi-asserted-by":"publisher","first-page":"698","DOI":"10.1007\/s00453-017-0288-2","volume":"80","author":"W Hon","year":"2018","unstructured":"Hon, W., Lam, T.W., Shah, R., Thankachan, S.V., Ting, H., Yang, Y.: Dictionary matching with a bounded gap in pattern or in text. Algorithmica 80(2), 698\u2013713 (2018)","journal-title":"Algorithmica"},{"key":"851_CR34","doi-asserted-by":"crossref","unstructured":"Amir, A., Levy, A., Porat, E., Shalom, B.R.: Dictionary matching with one gap. In: The Proceedings of the 25th Symposium on Combinatorial Pattern Matching (CPM), pp.\u00a011\u201320 (2014)","DOI":"10.1007\/978-3-319-07566-2_2"},{"key":"851_CR35","doi-asserted-by":"crossref","unstructured":"Abboud, A., Williams, V.V.: Popular conjectures imply strong lower bounds for dynamic problems. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS. pp. 434\u2013443 (2014)","DOI":"10.1109\/FOCS.2014.53"},{"key":"851_CR36","doi-asserted-by":"crossref","unstructured":"Gr\u00f8nlund, A., Pettie, S.: Threesomes, degenerates, and love triangles. FOCS 621\u2013630 (2014)","DOI":"10.1109\/FOCS.2014.72"},{"key":"851_CR37","doi-asserted-by":"crossref","unstructured":"Kopelowitz, T., Pettie, S., Porat, E.: Higher lower bounds from the 3sum conjecture. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA (2016)","DOI":"10.1137\/1.9781611974331.ch89"},{"key":"851_CR38","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M.: Towards polynomial lower bounds for dynamic problems. STOC 603\u2013610 (2010)","DOI":"10.1145\/1806689.1806772"},{"key":"851_CR39","doi-asserted-by":"crossref","unstructured":"Bj\u00f8rklund, A., Pagh, R., Vassilevska Williams, V., Zwick, U.: Listing triangles. In: Proceedings 41st Int\u2019l Colloquium on Automata, Languages, and Programming (ICALP (I)), pp.\u00a0223\u2013234 (2014)","DOI":"10.1007\/978-3-662-43948-7_19"},{"key":"851_CR40","doi-asserted-by":"crossref","unstructured":"Itai, A., Rodeh, M.: Finding a minimum circuit in a graph 7(4), 413\u2013423 (1978)","DOI":"10.1137\/0207033"},{"issue":"1","key":"851_CR41","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)"},{"key":"851_CR42","doi-asserted-by":"crossref","unstructured":"Pettie, S., Kopelowitz, T., Porat, E.: Dynamic set intersection. WADS (2015)","DOI":"10.1007\/978-3-319-21840-3_39"},{"issue":"40\u201342","key":"851_CR43","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."},{"issue":"1","key":"851_CR44","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":"851_CR45","doi-asserted-by":"publisher","first-page":"104633","DOI":"10.1016\/j.ic.2020.104633","volume":"275","author":"A Amir","year":"2020","unstructured":"Amir, A., Levy, A., Porat, E., Shalom, B.R.: Online recognition of dictionary with one gap. Inf. Comput. 275, 104633 (2020)","journal-title":"Inf. Comput."},{"issue":"6","key":"851_CR46","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":"3","key":"851_CR47","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0020-0190(94)90086-8","volume":"49","author":"A Amir","year":"1994","unstructured":"Amir, A., Farach, M., Muthukrishnan, S.: Alphabet dependence in parameterized matching. Inf. Process. Lett. 49(3), 111\u2013115 (1994)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"851_CR48","doi-asserted-by":"publisher","first-page":"1343","DOI":"10.1137\/S0097539793246707","volume":"26","author":"BS Baker","year":"1997","unstructured":"Baker, B.S.: Parameterized duplication in strings: algorithms and an application to software maintenance. SIAM J. Comput. 26(5), 1343\u20131362 (1997)","journal-title":"SIAM J. Comput."},{"key":"851_CR49","unstructured":"Deguchi, S., Higashijima, F., Bannai, H., Inenaga, S., Takeda, M.: Parameterized suffix arrays for binary strings. In: Proceedings of the Prague Stringology Conference (PSC) (Prague, Czech Republic), September 1\u20133, pp.\u00a084\u201394 (2008)"},{"issue":"2","key":"851_CR50","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1145\/301970.301973","volume":"46","author":"P Ferragina","year":"1999","unstructured":"Ferragina, P., Grossi, R.: The string b-tree: a new data structure for string search in external memory and its applications. J. ACM 46(2), 236\u2013280 (1999)","journal-title":"J. ACM"},{"key":"851_CR51","unstructured":"Ganguly, A., Hon, W., Shah, R.: A framework for dynamic parameterized dictionary matching. In: 15th Scandinavian Symposium and Workshops on Algorithm Theory SWAT (Reykjavik, Iceland), June 22\u201324, pp.\u00a010:1\u201310:14 (2016)"},{"issue":"51","key":"851_CR52","doi-asserted-by":"publisher","first-page":"5347","DOI":"10.1016\/j.tcs.2009.09.011","volume":"410","author":"O Keller","year":"2009","unstructured":"Keller, O., Kopelowitz, T., Lewenstein, M.: On the longest common parameterized subsequence. Theor. Comput. Sci. 410(51), 5347\u20135353 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"851_CR53","doi-asserted-by":"crossref","unstructured":"Lewenstein, M.: Parameterized pattern matching. Encyclopedia of Algorithms 1525\u20131530,(2016)","DOI":"10.1007\/978-1-4939-2864-4_282"},{"key":"851_CR54","unstructured":"Mendivelso, J., Pinz\u00f3n, Y.: Parameterized matching: Solutions and extensions. In: Proceedings of the Prague Stringology Conference (PSC) (Prague, Czech Republic), August 24\u201326, pp.\u00a0118\u2013131 (2015)"},{"issue":"2","key":"851_CR55","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"DE Willard","year":"1983","unstructured":"Willard, D.E.: Log-logarithmic worst-case range queries are possible in space $$\\theta (n)$$. Inf. Process. Lett. 17(2), 81\u201384 (1983)","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00851-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00851-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00851-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,3]],"date-time":"2024-09-03T11:29:38Z","timestamp":1725362978000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00851-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,6]]},"references-count":55,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["851"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00851-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,7,6]]},"assertion":[{"value":"4 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}