{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T01:42:57Z","timestamp":1725500577167},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540775652"},{"type":"electronic","value":"9783540775669"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-77566-9_31","type":"book-chapter","created":{"date-parts":[[2008,1,5]],"date-time":"2008-01-05T06:18:43Z","timestamp":1199513923000},"page":"364-375","source":"Crossref","is-referenced-by-count":1,"title":["Computing Longest Common Substring and All Palindromes from Compressed Strings"],"prefix":"10.1007","author":[{"given":"Wataru","family":"Matsubara","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Akira","family":"Ishino","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ayumi","family":"Shinohara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomoyuki","family":"Nakamura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuo","family":"Hashimoto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"31_CR1","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"IT-23","author":"J. Ziv","year":"1977","unstructured":"Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Trans. Info. Theory\u00a0IT-23(3), 337\u2013349 (1977)","journal-title":"IEEE Trans. Info. Theory"},{"issue":"5","key":"31_CR2","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-length coding. IEEE Trans. Info. Theory\u00a024(5), 530\u2013536 (1978)","journal-title":"IEEE Trans. Info. Theory"},{"issue":"4","key":"31_CR3","doi-asserted-by":"publisher","first-page":"1227","DOI":"10.1109\/18.850665","volume":"46","author":"J. Kieffer","year":"2000","unstructured":"Kieffer, J., Yang, E., Nelson, G., Cosman, P.: Universal lossless compression via multilevel pattern matching. IEEE Trans. Info. Theory\u00a046(4), 1227\u20131245 (2000)","journal-title":"IEEE Trans. Info. Theory"},{"key":"31_CR4","first-page":"244","volume-title":"DCC 1994","author":"C.G. Nevill-Manning","year":"1994","unstructured":"Nevill-Manning, C.G., Witten, I.H., Maulsby, D.L.: Compression by induction of hierarchical grammars. In: DCC 1994, pp. 244\u2013253. IEEE Press, Los Alamitos (1994)"},{"key":"31_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1007\/3-540-61422-2_148","volume-title":"Algorithm Theory - SWAT \u201996","author":"L. Gasieniec","year":"1996","unstructured":"Gasieniec, L., Karpinski, M., Plandowski, W., Rytter, W.: Efficient algorithms for Lempel-Ziv encoding. In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol.\u00a01097, pp. 392\u2013403. Springer, Heidelberg (1996)"},{"key":"31_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/978-3-540-27836-8_5","volume-title":"Automata, Languages and Programming","author":"W. Rytter","year":"2004","unstructured":"Rytter, W.: Grammar compression, lz-encodings, and string algorithms with implicit input. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 15\u201327. Springer, Heidelberg (2004)"},{"key":"31_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/978-3-540-30550-7_19","volume-title":"Developments in Language Theory","author":"S. Inenaga","year":"2004","unstructured":"Inenaga, S., Shinohara, A., Takeda, M.: An efficient pattern matching algorithm on a subclass of context free grammars. In: Calude, C.S., Calude, E., Dinneen, M.J. (eds.) DLT 2004. LNCS, vol.\u00a03340, pp. 225\u2013236. Springer, Heidelberg (2004)"},{"key":"31_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/BFb0049431","volume-title":"Algorithms - ESA \u201994","author":"W. Plandowski","year":"1994","unstructured":"Plandowski, W.: Testing equivalence of morphisms on context-free languages. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol.\u00a0855, pp. 460\u2013470. Springer, Heidelberg (1994)"},{"key":"31_CR9","first-page":"172","volume":"4","author":"M. Karpinski","year":"1997","unstructured":"Karpinski, M., Rytter, W., Shinohara, A.: An efficient pattern-matching algorithm for strings with short descriptions. Nordic Journal of Computing\u00a04, 172\u2013186 (1997)","journal-title":"Nordic Journal of Computing"},{"key":"31_CR10","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"CPM 1997","author":"M. Miyazaki","year":"1997","unstructured":"Miyazaki, M., Shinohara, A., Takeda, M.: An improved pattern matching algorithm for strings in terms of straight-line programs. In: Hein, J., Apostolico, A. (eds.) CPM 1997. LNCS, vol.\u00a01264, pp. 1\u201311. Springer, Heidelberg (1997)"},{"key":"31_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1007\/978-3-540-73437-6_24","volume-title":"CPM 2007","author":"Y. Lifshits","year":"2007","unstructured":"Lifshits, Y.: Processing compressed texts: A tractability border. In: CPM 2007. LNCS, vol.\u00a04580, pp. 228\u2013240. Springer, Heidelberg (2007)"},{"key":"31_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1007\/11821069_59","volume-title":"Mathematical Foundations of Computer Science 2006","author":"Y. Lifshits","year":"2006","unstructured":"Lifshits, Y., Lohrey, M.: Querying and embedding compressed texts. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol.\u00a04162, pp. 681\u2013692. Springer, Heidelberg (2006)"},{"key":"31_CR13","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0304-3975(94)00083-U","volume":"141","author":"A. Apostolico","year":"1995","unstructured":"Apostolico, A., Breslauer, D., Galil, Z.: Parallel detection of all palindromes in a string. Theoretical Computer Science\u00a0141, 163\u2013173 (1995)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2008: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77566-9_31.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:44:56Z","timestamp":1619520296000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77566-9_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540775652","9783540775669"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77566-9_31","relation":{},"subject":[]}}