{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:36:18Z","timestamp":1725489378168},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540734369"},{"type":"electronic","value":"9783540734376"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73437-6_8","type":"book-chapter","created":{"date-parts":[[2007,8,13]],"date-time":"2007-08-13T13:36:44Z","timestamp":1187012204000},"page":"52-62","source":"Crossref","is-referenced-by-count":3,"title":["Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts"],"prefix":"10.1007","author":[{"given":"Philip","family":"Bille","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Fagerberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Inge Li","family":"G\u00f8rtz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"Amir, A., Benson, G.: Efficient two-dimensional compressed matching. In: Proceedings of the 2nd Data Compression Conference, pp. 279\u2013288 (1992)","DOI":"10.1109\/DCC.1992.227453"},{"key":"8_CR2","unstructured":"Amir, A., Benson, G.: Two-dimensional periodicity and its applications. In: Proceedings of the 3rd Symposium on Discrete algorithms, pp. 440\u2013452 (1992)"},{"issue":"2","key":"8_CR3","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1006\/jcss.1996.0023","volume":"52","author":"A. Amir","year":"1996","unstructured":"Amir, A., Benson, G., Farach, M.: Let sleeping files lie: pattern matching in Z-compressed files. J. Comput. Syst. Sci.\u00a052(2), 299\u2013307 (1996)","journal-title":"J. Comput. Syst. Sci."},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"Bille, P.: New algorithms for regular expression matching. In: Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, pp. 643\u2013654 (2006)","DOI":"10.1007\/11786986_56"},{"key":"8_CR5","unstructured":"Bille, P., Fagerberg, R., G\u00f8rtz, I.L.: Improved approximate string matching and regular expression matching on ziv-lempel compressed texts (2007), Draft of full version available at arxiv.org\/cs\/DS\/0609085"},{"key":"8_CR6","unstructured":"Bille, P., Farach-Colton, M.: Fast and compact regular expression matching, Submitted to a journal (2005), Preprint availiable at arxiv.org\/cs\/0509069"},{"issue":"6","key":"8_CR7","doi-asserted-by":"publisher","first-page":"1761","DOI":"10.1137\/S0097539700370527","volume":"31","author":"R. Cole","year":"2002","unstructured":"Cole, R., Hariharan, R.: Approximate string matching: A simpler faster algorithm. SIAM J. Comput.\u00a031(6), 1761\u20131782 (2002)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"8_CR8","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1137\/S0097539791194094","volume":"23","author":"M. Dietzfelbinger","year":"1994","unstructured":"Dietzfelbinger, M., Karlin, A., Mehlhorn, K., auf der Heide, F.M., Rohnert, H., Tarjan, R.: Dynamic perfect hashing: Upper and lower bounds. SIAM J. Comput.\u00a023(4), 738\u2013761 (1994)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"8_CR9","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1007\/PL00009202","volume":"20","author":"M. Farach","year":"1998","unstructured":"Farach, M., Thorup, M.: String matching in Lempel-Ziv compressed strings. Algorithmica\u00a020(4), 388\u2013404 (1998)","journal-title":"Algorithmica"},{"issue":"3-4","key":"8_CR10","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/S1570-8667(03)00032-7","volume":"1","author":"J. K\u00e4rkk\u00e4inen","year":"2003","unstructured":"K\u00e4rkk\u00e4inen, J., Navarro, G., Ukkonen, E.: Approximate string matching on Ziv-Lempel compressed text. J. Discrete Algorithms\u00a01(3-4), 313\u2013338 (2003)","journal-title":"J. Discrete Algorithms"},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Kida, T., Takeda, M., Shinohara, A., Miyazaki, M., Arikawa, S.: Multiple pattern matching in LZW compressed text. In: Proceedings of the 8th Data Compression Conference, pp. 103\u2013112 (1998)","DOI":"10.1109\/DCC.1998.672136"},{"issue":"2","key":"8_CR12","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0196-6774(89)90010-2","volume":"10","author":"G.M. Landau","year":"1989","unstructured":"Landau, G.M., Vishkin, U.: Fast parallel and serial approximate string matching. J. Algorithms\u00a010(2), 157\u2013169 (1989)","journal-title":"J. Algorithms"},{"issue":"4","key":"8_CR13","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/s00453-002-1005-2","volume":"35","author":"V. M\u00e4kinen","year":"2003","unstructured":"M\u00e4kinen, V., Ukkonen, E., Navarro, G.: Approximate matching of run-length compressed strings. Algorithmica\u00a035(4), 347\u2013369 (2003)","journal-title":"Algorithmica"},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"Matsumoto, T., Kida, T., Takeda, M., Shinohara, A., Arikawa, S.: Bit-parallel approach to approximate string matching in compressed texts. In: Proceedings of the 7th International Symposium on String Processing and Information Retrieval, pp. 221\u2013228 (2000)","DOI":"10.1109\/SPIRE.2000.878198"},{"issue":"2","key":"8_CR15","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1145\/128749.128755","volume":"39","author":"E.W. Myers","year":"1992","unstructured":"Myers, E.W.: A four-russian algorithm for regular expression pattern matching. J. ACM\u00a039(2), 430\u2013448 (1992)","journal-title":"J. ACM"},{"issue":"1","key":"8_CR16","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/375360.375365","volume":"33","author":"G. Navarro","year":"2001","unstructured":"Navarro, G.: A guided tour to approximate string matching. ACM Comput. Surv.\u00a033(1), 31\u201388 (2001)","journal-title":"ACM Comput. Surv."},{"issue":"5-6","key":"8_CR17","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/S1570-8667(03)00036-4","volume":"1","author":"G. Navarro","year":"2003","unstructured":"Navarro, G.: Regular expression searching on compressed text. J. Discrete Algorithms\u00a01(5-6), 423\u2013443 (2003)","journal-title":"J. Discrete Algorithms"},{"key":"8_CR18","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1109\/DCC.2001.917177","volume-title":"Proceedings of the Data Compression Conference (DCC 2001)","author":"G. Navarro","year":"2001","unstructured":"Navarro, G., Kida, T., Takeda, M., Shinohara, A., Arikawa, S.: Faster approximate string matching over compressed text. In: Proceedings of the Data Compression Conference (DCC 2001), p. 459. IEEE Computer Society, Washington, DC, USA (2001)"},{"key":"8_CR19","doi-asserted-by":"crossref","unstructured":"Navarro, G., Raffinot, M.: A general practical approach to pattern matching over Ziv-Lempel compressed text. Technical Report TR\/DCC-98-12, Dept. of Computer Science, Univ. of Chile (1998)","DOI":"10.1007\/3-540-48452-3_2"},{"key":"8_CR20","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/0196-6774(80)90016-4","volume":"1","author":"P. Sellers","year":"1980","unstructured":"Sellers, P.: The theory and computation of evolutionary distances: Pattern recognition. J. Algorithms\u00a01, 359\u2013373 (1980)","journal-title":"J. Algorithms"},{"key":"8_CR21","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1145\/363347.363387","volume":"11","author":"K. Thompson","year":"1968","unstructured":"Thompson, K.: Programming techniques: Regular expression search algorithm. Commun. ACM\u00a011, 419\u2013422 (1968)","journal-title":"Commun. ACM"},{"issue":"6","key":"8_CR22","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1109\/MC.1984.1659158","volume":"17","author":"T.A. Welch","year":"1984","unstructured":"Welch, T.A.: A technique for high-performance data compression. IEEE Computer\u00a017(6), 8\u201319 (1984)","journal-title":"IEEE Computer"},{"issue":"3","key":"8_CR23","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"23","author":"J. Ziv","year":"1977","unstructured":"Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Trans. Inform. Theory\u00a023(3), 337\u2013343 (1977)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"5","key":"8_CR24","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"24","author":"J. Ziv","year":"1978","unstructured":"Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding. IEEE Trans. Inform. Theory\u00a024(5), 530\u2013536 (1978)","journal-title":"IEEE Trans. Inform. Theory"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73437-6_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:12:15Z","timestamp":1619503935000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73437-6_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540734369","9783540734376"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73437-6_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}