{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T08:33:26Z","timestamp":1780389206979,"version":"3.54.1"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319075655","type":"print"},{"value":"9783319075662","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-07566-2_2","type":"book-chapter","created":{"date-parts":[[2014,6,12]],"date-time":"2014-06-12T03:50:31Z","timestamp":1402545031000},"page":"11-20","source":"Crossref","is-referenced-by-count":8,"title":["Dictionary Matching with One Gap"],"prefix":"10.1007","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Avivit","family":"Levy","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ely","family":"Porat","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"B. Riva","family":"Shalom","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"6","key":"2_CR1","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"A.V. Aho","year":"1975","unstructured":"Aho, A.V., Corasick, M.J.: Efficient string matching: an aid to bibliographic search. Comm. ACM\u00a018(6), 333\u2013340 (1975)","journal-title":"Comm. ACM"},{"key":"2_CR2","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1006\/jagm.2000.1081","volume":"36","author":"A. Amir","year":"2000","unstructured":"Amir, A., Calinescu, G.: Alphabet independent and dictionary scaled matching. J. of Algorithms\u00a036, 34\u201362 (2000)","journal-title":"J. of Algorithms"},{"issue":"2","key":"2_CR3","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., Giancarlo, R., Galil, Z., Park, K.: Dynamic dictionary matching. Journal of Computer and System Sciences\u00a049(2), 208\u2013222 (1994)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"2_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. Information and Computation\u00a0119(2), 258\u2013282 (1995)","journal-title":"Information and Computation"},{"key":"2_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/3-540-48447-7_19","volume-title":"Algorithms and Data Structures","author":"A. Amir","year":"1999","unstructured":"Amir, A., Keselman, D., Landau, G.M., Lewenstein, M., Lewenstein, N., Rodeh, M.: Indexing and dictionary matching with one error. In: Dehne, F., Gupta, A., Sack, J.-R., Tamassia, R. (eds.) WADS 1999. LNCS, vol.\u00a01663, pp. 181\u2013192. Springer, Heidelberg (1999)"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"Bille, P., G\u00f8rtz, I.L., Vildh\u00f8j, H.W., Wind, D.K.: String matching with variable length gaps. Theoretical Computer Science\u00a0(443), 25\u201334 (2012)","DOI":"10.1016\/j.tcs.2012.03.029"},{"key":"2_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/978-3-642-02927-1_16","volume-title":"Automata, Languages and Programming","author":"P. Bille","year":"2009","unstructured":"Bille, P., Thorup, M.: Faster regular expression matching. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 171\u2013182. Springer, Heidelberg (2009)"},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"Bille, P., Thorup, M.: Regular expression matching with multi-strings and intervals. In: Proc. 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1297\u20131308 (2010)","DOI":"10.1137\/1.9781611973075.104"},{"key":"2_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/3-540-61258-0_6","volume-title":"Combinatorial Pattern Matching","author":"G.S. Brodal","year":"1996","unstructured":"Brodal, G.S., Gasieniec, L.: Approximate dictionary queries. In: Hirschberg, D.S., Meyers, G. (eds.) CPM 1996. LNCS, vol.\u00a01075, pp. 65\u201374. Springer, Heidelberg (1996)"},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: Proc. 36th Annual ACM Symposium on the Theory of Computing (STOC), pp. 91\u2013100. ACM Press (2004)","DOI":"10.1145\/1007352.1007374"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Larsen, K.G., P\u01cetra\u015fcu, M.: Orthogonal range searching on the ram, revisited. In: Proc. 27th ACM Symposium on Computational Geometry (SoCG), pp. 1\u201310 (2011)","DOI":"10.1145\/1998196.1998198"},{"issue":"4","key":"2_CR12","doi-asserted-by":"publisher","first-page":"338","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.\u00a011(4), 338\u2013349 (2008)","journal-title":"Inf. Retr."},{"key":"2_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/978-3-642-20662-7_7","volume-title":"Experimental Algorithms","author":"T. Haapasalo","year":"2011","unstructured":"Haapasalo, T., Silvasti, P., Sippu, S., Soisalon-Soininen, E.: Online Dictionary Matching with Variable-Length Gaps. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol.\u00a06630, pp. 76\u201387. Springer, Heidelberg (2011)"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"Hofmann, K., Bucher, P., Falquet, L., Bairoch, A.: The PROSITE database. Nucleic Acids Res.\u00a0(27), 215\u2013219 (1999)","DOI":"10.1093\/nar\/27.1.215"},{"key":"2_CR15","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., 30 Corporate Dr., Burlington, MA 01803 (2008), e-edition: \n                  \n                    http:\/\/www.sciencedirect.com\/science\/book\/9781597492072"},{"issue":"12","key":"2_CR16","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. Theoret. Comput. Sci.\u00a0178(12), 129\u2013154 (1997)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"2_CR17","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"E.M. McCreight","year":"1976","unstructured":"McCreight, E.M.: A Space-Economical Suffix Tree Construction Algorithm. Journal of the ACM\u00a023(2), 262\u2013272 (1976)","journal-title":"Journal of the ACM"},{"issue":"8","key":"2_CR18","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. Bio.\u00a012(8), 1065\u20131082 (2005)","journal-title":"J. Comput. Bio."},{"issue":"2","key":"2_CR19","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1145\/128749.128755","volume":"39","author":"G. Myers","year":"1992","unstructured":"Myers, G.: A four-russian algorithm for regular expression pattern matching. J. ACM\u00a039(2), 430\u2013448 (1992)","journal-title":"J. ACM"},{"issue":"3","key":"2_CR20","first-page":"299","volume":"9","author":"G. Myers","year":"1993","unstructured":"Myers, G., Mehldau, G.: A system for pattern matching applications on biosequences. CABIOS\u00a09(3), 299\u2013314 (1993)","journal-title":"CABIOS"},{"issue":"3","key":"2_CR21","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/S0304-3975(03)00053-7","volume":"304","author":"J.C. Naa","year":"2003","unstructured":"Naa, J.C., Apostolico, A., Iliopoulos, C.S., Park, K.: Truncated suffix trees and their application to data compression. Theoretical Computer Science\u00a0304(3), 87\u2013101 (2003)","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"2_CR22","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. Bio.\u00a010(6), 903\u2013923 (2003)","journal-title":"J. Comput. Bio."},{"issue":"2","key":"2_CR23","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/s00453-004-1120-3","volume":"41","author":"G. Navarro","year":"2004","unstructured":"Navarro, G., Raffinot, M.: New techniques for regular expression searching. Algorithmica\u00a041(2), 89\u2013116 (2004)","journal-title":"Algorithmica"},{"key":"2_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/11809678_17","volume-title":"Computing and Combinatorics","author":"M.S. Rahman","year":"2006","unstructured":"Rahman, M.S., Iliopoulos, C.S., Lee, I., Mohamed, M., Smyth, W.F.: Finding patterns with variable length gaps or don\u2019t cares. In: Chen, D.Z., Lee, D.T. (eds.) COCOON 2006. LNCS, vol.\u00a04112, pp. 146\u2013155. Springer, Heidelberg (2006)"},{"issue":"3","key":"2_CR25","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01206331","volume":"14","author":"E. Ukkonen","year":"1995","unstructured":"Ukkonen, E.: On-line construction of suffix trees. Algorithmica\u00a014(3), 249\u2013260 (1995)","journal-title":"Algorithmica"},{"key":"2_CR26","doi-asserted-by":"crossref","unstructured":"van Emde Boas, P.: Preserving order in a forest in less than logarithmic time. In: Proceedings of the 16th Annual Symposium on Foundations of Computer Science, pp. 75\u201384 (1975)","DOI":"10.1109\/SFCS.1975.26"},{"key":"2_CR27","unstructured":"Verint. Packet intrusion detection. Personal communication (2013)"},{"key":"2_CR28","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithm. In: Proc. 14 IEEE Symposium on Switching and Automata Theory, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"},{"key":"2_CR29","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. Inform. Process. Letters\u00a0110, 216\u2013220 (2010)","journal-title":"Inform. Process. Letters"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-07566-2_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T02:00:29Z","timestamp":1558922429000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-07566-2_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319075655","9783319075662"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-07566-2_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}