{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T05:23:55Z","timestamp":1725600235588},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642222993"},{"type":"electronic","value":"9783642223006"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22300-6_52","type":"book-chapter","created":{"date-parts":[[2011,8,9]],"date-time":"2011-08-09T12:41:31Z","timestamp":1312893691000},"page":"619-630","source":"Crossref","is-referenced-by-count":0,"title":["Succinct 2D Dictionary Matching with No Slowdown"],"prefix":"10.1007","author":[{"given":"Shoshana","family":"Neuburger","sequence":"first","affiliation":[]},{"given":"Dina","family":"Sokol","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"52_CR1","doi-asserted-by":"crossref","unstructured":"Amir, A., Benson, G., Farach, M.: An alphabet independent approach to two-dimensional pattern matching. SICOMP: SIAM Journal on Computing\u00a023 (1994)","DOI":"10.1137\/S0097539792226321"},{"key":"52_CR2","doi-asserted-by":"crossref","unstructured":"Baker, T.J.: A technique for extending rapid exact-match string matching to arrays of more than one dimension. SIAM J. Comp.\u00a0(7), 533\u2013541 (1978)","DOI":"10.1137\/0207043"},{"key":"52_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/978-3-642-13509-5_9","volume-title":"Combinatorial Pattern Matching","author":"D. Belazzougui","year":"2010","unstructured":"Belazzougui, D.: Succinct dictionary matching with no slowdown. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol.\u00a06129, pp. 88\u2013100. Springer, Heidelberg (2010)"},{"key":"52_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"LATIN 2000: Theoretical Informatics","author":"M.A. Bender","year":"2000","unstructured":"Bender, M.A., Farach-Colton, M.: The lca problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol.\u00a01776, pp. 88\u201394. Springer, Heidelberg (2000)"},{"issue":"5","key":"52_CR5","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/0020-0190(77)90017-5","volume":"6","author":"R.S. Bird","year":"1977","unstructured":"Bird, R.S.: Two dimensional pattern matching. Information Processing Letters\u00a06(5), 168\u2013170 (1977)","journal-title":"Information Processing Letters"},{"key":"52_CR6","doi-asserted-by":"crossref","unstructured":"Chan, H.L., Hon, W.K., Lam, T.W., Sadakane, K.: Compressed indexes for dynamic text collections. ACM Transactions on Algorithms\u00a03(2) (2007)","DOI":"10.1145\/1240233.1240244"},{"key":"52_CR7","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Gasieniec, L., Plandowski, W., Rytter, W.: Two-dimensional pattern matching in linear time and small space. In: STACS: Annual Symposium on Theoretical Aspects of Computer Science (1995)","DOI":"10.1007\/3-540-59042-0_72"},{"issue":"3","key":"52_CR8","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1145\/116825.116845","volume":"38","author":"M. Crochemore","year":"1991","unstructured":"Crochemore, M., Perrin, D.: Two-way string-matching. J. ACM\u00a038(3), 650\u2013674 (1991)","journal-title":"J. ACM"},{"key":"52_CR9","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Structuring labeled trees for optimal succinctness, and beyond. In: FOCS 2005, pp. 184\u2013196 (2005)","DOI":"10.1109\/SFCS.2005.69"},{"key":"52_CR10","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1145\/800076.802463","volume-title":"STOC 1981: Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing","author":"Z. Galil","year":"1981","unstructured":"Galil, Z., Seiferas, J.: Time-space-optimal string matching (preliminary report). In: STOC 1981: Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing, pp. 106\u2013113. ACM, New York (1981)"},{"key":"52_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/978-3-540-27801-6_9","volume-title":"Combinatorial Pattern Matching","author":"L. G\u0105sieniec","year":"2004","unstructured":"G\u0105sieniec, L., Kolpakov, R.: Real-time string matching in sublinear space. In: Sahinalp, S.C., Muthukrishnan, S.M., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol.\u00a03109, pp. 117\u2013129. Springer, Heidelberg (2004)"},{"key":"52_CR12","doi-asserted-by":"crossref","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SICOMP: SIAM Journal on Computing\u00a013 (1984)","DOI":"10.1137\/0213024"},{"key":"52_CR13","doi-asserted-by":"crossref","unstructured":"Hon, W.-K., Ku, T.-H., Shah, R., Thankachan, S.V., Vitter, J.S.: Faster compressed dictionary matching. In: SPIRE, pp. 191\u2013200 (2010)","DOI":"10.1007\/978-3-642-16321-0_19"},{"key":"52_CR14","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: DCC, pp. 23\u201332 (2008)","DOI":"10.1109\/DCC.2008.62"},{"key":"52_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1034","DOI":"10.1007\/978-3-642-10631-6_104","volume-title":"Algorithms and Computation","author":"W.-K. Hon","year":"2009","unstructured":"Hon, W.-K., Lam, T., Shah, R., Tam, S.-L., Vitter, J.S.: Succinct index for dynamic dictionary matching. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol.\u00a05878, pp. 1034\u20131043. Springer, Heidelberg (2009)"},{"key":"52_CR16","doi-asserted-by":"crossref","unstructured":"Main, M.G., Lorentz, R.J.: An O(n log n) algorithm for finding all repetitions in a string. ALGORITHMS: Journal of Algorithms\u00a05 (1984)","DOI":"10.1016\/0196-6774(84)90021-X"},{"key":"52_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/978-3-642-13509-5_4","volume-title":"Combinatorial Pattern Matching","author":"S. Neuburger","year":"2010","unstructured":"Neuburger, S., Sokol, D.: Small-space 2D compressed dictionary matching. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol.\u00a06129, pp. 27\u201339. Springer, Heidelberg (2010)"},{"issue":"1-3","key":"52_CR18","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1016\/S0304-3975(02)00590-X","volume":"299","author":"W. Rytter","year":"2003","unstructured":"Rytter, W.: On maximal suffixes and constant-space linear-time versions of kmp algorithm. Theor. Comput. Sci.\u00a0299(1-3), 763\u2013774 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"52_CR19","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"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22300-6_52","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T22:54:10Z","timestamp":1560466450000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22300-6_52"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642222993","9783642223006"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22300-6_52","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}