{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T07:07:32Z","timestamp":1725865652606},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319460482"},{"type":"electronic","value":"9783319460499"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-319-46049-9_13","type":"book-chapter","created":{"date-parts":[[2016,9,20]],"date-time":"2016-09-20T15:02:06Z","timestamp":1474383726000},"page":"133-144","source":"Crossref","is-referenced-by-count":1,"title":["Dynamic and Approximate Pattern Matching in 2D"],"prefix":"10.1007","author":[{"given":"Rapha\u00ebl","family":"Clifford","sequence":"first","affiliation":[]},{"given":"Allyx","family":"Fontaine","sequence":"additional","affiliation":[]},{"given":"Tatiana","family":"Starikovskaya","sequence":"additional","affiliation":[]},{"given":"Hjalte Wedel","family":"Vildh\u00f8j","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,9,21]]},"reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. In: STOC 1996, pp. 20\u201329. ACM (1996)","DOI":"10.1145\/237814.237823"},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"Amir, A., Benson, G.: Efficient two-dimensional compressed matching. In: Data Compression Conference, DCC 1992, pp. 279\u2013288. IEEE (1992)","DOI":"10.1109\/DCC.1992.227453"},{"issue":"1","key":"13_CR3","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1137\/S0097539795298321","volume":"27","author":"A Amir","year":"1998","unstructured":"Amir, A., Benson, G.: Two-dimensional periodicity in rectangular arrays. SIAM J. Comp. 27(1), 90\u2013106 (1998)","journal-title":"SIAM J. Comp."},{"issue":"2","key":"13_CR4","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1006\/jagm.1997.0860","volume":"24","author":"A Amir","year":"1997","unstructured":"Amir, A., Benson, G., Farach, M.: Optimal two-dimensional compressed matching. J. Algorithms 24(2), 354\u2013379 (1997)","journal-title":"J. Algorithms"},{"issue":"1","key":"13_CR5","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/j.tcs.2003.10.039","volume":"314","author":"A Amir","year":"2004","unstructured":"Amir, A., Butman, A., Crochemore, M., Landau, G.M., Schaps, M.: Two-dimensional pattern matching with rotations. Theor. Comput. Sci. 314(1), 173\u2013187 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"13_CR6","unstructured":"Amir, A., Farach, M.: Efficient 2-dimensional approximate matching of non-rectangular figures. In: SODA, pp. 212\u2013223 (1991)"},{"issue":"1","key":"13_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/inco.1995.1047","volume":"118","author":"A Amir","year":"1995","unstructured":"Amir, A., Farach, M.: Efficient 2-dimensional approximate matching of half-rectangular figures. Inf. Comput. 118(1), 1\u201311 (1995)","journal-title":"Inf. Comput."},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"Amir, A., Landau, G.M., Lewenstein, M., Sokol, D.: Dynamic text and static pattern matching. ACM Trans. Algorithms (TALG), 3(2) (2007)","DOI":"10.1145\/1240233.1240242"},{"issue":"3","key":"13_CR9","doi-asserted-by":"crossref","first-page":"1361","DOI":"10.1016\/S0304-3975(02)00041-5","volume":"290","author":"A Amir","year":"2003","unstructured":"Amir, A., Landau, G.M., Sokol, D.: Inplace run-length 2D compressed search. Theor. Comput. Sci. 290(3), 1361\u20131383 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"13_CR10","doi-asserted-by":"crossref","unstructured":"Andoni, A., Indyk, P.: Efficient algorithms for substring near neighbor problem. In: SODA 2006, pp. 1203\u20131212 (2006)","DOI":"10.1145\/1109557.1109690"},{"issue":"4","key":"13_CR11","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1137\/0207043","volume":"7","author":"TP Baker","year":"1978","unstructured":"Baker, T.P.: A technique for extending rapid exact-match string matching to arrays of more than one dimension. SIAM J. Comp. 7(4), 533\u2013541 (1978)","journal-title":"SIAM J. Comp."},{"issue":"5","key":"13_CR12","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1016\/0020-0190(77)90017-5","volume":"6","author":"RS Bird","year":"1977","unstructured":"Bird, R.S.: Two dimensional pattern matching. IPL 6(5), 168\u2013170 (1977)","journal-title":"IPL"},{"issue":"4","key":"13_CR13","doi-asserted-by":"crossref","first-page":"894","DOI":"10.1137\/S0097539700370539","volume":"34","author":"R Cole","year":"2005","unstructured":"Cole, R., Hariharan, R.: Dynamic LCA queries on trees. SIAM J. Comput. 34(4), 894\u2013923 (2005)","journal-title":"SIAM J. Comput."},{"key":"13_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/3-540-45452-7_20","volume-title":"Combinatorial Pattern Matching","author":"K Fredriksson","year":"2002","unstructured":"Fredriksson, K., Navarro, G., Ukkonen, E.: Optimal exact and fast approximate two dimensional pattern matching allowing rotations. In: Apostolico, A., Takeda, M. (eds.) CPM 2002. LNCS, vol. 2373, pp. 235\u2013248. Springer, Heidelberg (2002)"},{"key":"13_CR15","doi-asserted-by":"crossref","unstructured":"Galil, Z., Park, K.: Truly alphabet-independent two-dimensional pattern matching. In: FOCS 1992, pp. 247\u2013256 (1992)","DOI":"10.1109\/SFCS.1992.267767"},{"issue":"3","key":"13_CR16","doi-asserted-by":"crossref","first-page":"520","DOI":"10.1137\/S0097539792231982","volume":"24","author":"R Giancarlo","year":"1995","unstructured":"Giancarlo, R.: A generalization of the suffix tree to square matrices, with applications. SIAM J. Comp. 24(3), 520\u2013562 (1995)","journal-title":"SIAM J. Comp."},{"key":"13_CR17","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees and Sequences. Computer Science and Computational Biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees and Sequences. Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)"},{"issue":"2","key":"13_CR18","doi-asserted-by":"crossref","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."}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-46049-9_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T23:15:27Z","timestamp":1498346127000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-46049-9_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319460482","9783319460499"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-46049-9_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}