{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T22:29:12Z","timestamp":1772058552384,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642214578","type":"print"},{"value":"9783642214585","type":"electronic"}],"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-21458-5_27","type":"book-chapter","created":{"date-parts":[[2011,6,27]],"date-time":"2011-06-27T17:11:27Z","timestamp":1309194687000},"page":"309-322","source":"Crossref","is-referenced-by-count":13,"title":["Faster Subsequence and Don\u2019t-Care Pattern Matching on Compressed Texts"],"prefix":"10.1007","author":[{"given":"Takanori","family":"Yamamoto","sequence":"first","affiliation":[]},{"given":"Hideo","family":"Bannai","sequence":"additional","affiliation":[]},{"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[]},{"given":"Masayuki","family":"Takeda","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"27_CR1","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/0304-3975(91)90358-9","volume":"78","author":"R.A. Baeza-Yates","year":"1991","unstructured":"Baeza-Yates, R.A.: Searching subsequences. Theoretical Computer Science\u00a078(2), 363\u2013376 (1991)","journal-title":"Theoretical Computer Science"},{"issue":"30\u201332","key":"27_CR2","doi-asserted-by":"publisher","first-page":"2804","DOI":"10.1016\/j.tcs.2009.03.007","volume":"410","author":"P. Baturo","year":"2009","unstructured":"Baturo, P., Rytter, W.: Compressed string-matching in standard sturmian words. Theoretical Computer Science\u00a0410(30\u201332), 2804\u20132810 (2009)","journal-title":"Theoretical Computer Science"},{"key":"27_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/11753728_15","volume-title":"Computer Science \u2013 Theory and Applications","author":"P. C\u00e9gielski","year":"2006","unstructured":"C\u00e9gielski, P., Guessarian, I., Lifshits, Y., Matiyasevich, Y.: Window subsequence problems for compressed texts. In: Grigoriev, D., Harrison, J., Hirsch, E.A. (eds.) CSR 2006. LNCS, vol.\u00a03967, pp. 127\u2013136. Springer, Heidelberg (2006)"},{"key":"27_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-642-03816-7_21","volume-title":"Mathematical Foundations of Computer Science 2009","author":"F. Claude","year":"2009","unstructured":"Claude, F., Navarro, G.: Self-indexed text compression using straight-line programs. In: Kr\u00e1lovi\u010d, R., Niwi\u0144ski, D. (eds.) MFCS 2009. LNCS, vol.\u00a05734, pp. 235\u2013246. Springer, Heidelberg (2009)"},{"key":"27_CR5","unstructured":"Hermelin, D., Landau, G.M., Landau, S., Weimann, O.: A unified algorithm for accelerating edit-distance computation via text-compression. In: Proc. STACS 2009, pp. 529\u2013540 (2009)"},{"key":"27_CR6","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"},{"issue":"2","key":"27_CR7","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D.E. Knuth","year":"1977","unstructured":"Knuth, D.E., Morris, J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput.\u00a06(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"key":"27_CR8","first-page":"296","volume-title":"Proc. Data Compression Conference 1999","author":"N.J. Larsson","year":"1999","unstructured":"Larsson, N.J., Moffat, A.: Offline dictionary-based compression. In: Proc. Data Compression Conference 1999, pp. 296\u2013305. IEEE Computer Society Press, Los Alamitos (1999)"},{"key":"27_CR9","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)"},{"issue":"3","key":"27_CR10","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1023\/A:1009748302351","volume":"1","author":"H. Mannila","year":"1997","unstructured":"Mannila, H., Toivonen, H., Verkamo, A.I.: Discovery of frequent episodes in event sequences. Data Mining and Knowledge Discovery\u00a01(3), 259\u2013289 (1997)","journal-title":"Data Mining and Knowledge Discovery"},{"key":"27_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-63220-4_45","volume-title":"Combinatorial Pattern Matching","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: CPM 1997. LNCS, vol.\u00a01264, pp. 1\u201311. Springer, Heidelberg (1997)"},{"key":"27_CR12","first-page":"244","volume-title":"Data Compression Conference 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: Data Compression Conference 1994, pp. 244\u2013253. IEEE Computer Society Press, Los Alamitos (1994)"},{"key":"27_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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)"},{"issue":"5","key":"27_CR14","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1007\/s10958-009-9396-0","volume":"158","author":"A. Tiskin","year":"2009","unstructured":"Tiskin, A.: Faster subsequence recognition in compressed strings. J. Math. Sci.\u00a0158(5), 759\u2013769 (2009)","journal-title":"J. Math. Sci."},{"key":"27_CR15","doi-asserted-by":"crossref","unstructured":"Tiskin, A.: Towards approximate matching in compressed strings: Local subsequence recognition. In: Proc. CSR 2011 (to appear, 2011)","DOI":"10.1007\/978-3-642-20712-9_32"},{"issue":"3","key":"27_CR16","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 Transactions on Information Theory IT-23(3), 337\u2013349 (1977)","journal-title":"IEEE Transactions on Information Theory IT"},{"issue":"5","key":"27_CR17","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 Transactions on Information Theory\u00a024(5), 530\u2013536 (1978)","journal-title":"IEEE Transactions on Information Theory"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-21458-5_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,29]],"date-time":"2019-03-29T09:53:00Z","timestamp":1553853180000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-21458-5_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642214578","9783642214585"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-21458-5_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}