{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T08:38:39Z","timestamp":1780389519778,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662483497","type":"print"},{"value":"9783662483503","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-662-48350-3_45","type":"book-chapter","created":{"date-parts":[[2015,9,1]],"date-time":"2015-09-01T01:40:34Z","timestamp":1441071634000},"page":"533-544","source":"Crossref","is-referenced-by-count":17,"title":["Approximating LZ77 via Small-Space Multiple-Pattern Matching"],"prefix":"10.1007","author":[{"given":"Johannes","family":"Fischer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tomasz","family":"Kociumaka","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,11,12]]},"reference":[{"key":"45_CR1","unstructured":"Rabin-Karp algorithm \u2014 Wikipedia, The Free Encyclopedia. \n                    \n                      http:\/\/en.wikipedia.org\/w\/index.php?title=Rabin-Karp_algorithm&oldid=665980736"},{"issue":"6","key":"45_CR2","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"A.V. Aho","year":"1975","unstructured":"Aho, A.V., Corasick, M.J.: Efficient string matching: An aid to bibliographic search. Commun. ACM\u00a018(6), 333\u2013340 (1975)","journal-title":"Commun. ACM"},{"key":"45_CR3","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2012.11.040","volume":"483","author":"D. Breslauer","year":"2013","unstructured":"Breslauer, D., Grossi, R., Mignosi, F.: Simple real-time constant-space string matching. Theor. Comput. Sci.\u00a0483, 2\u20139 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"45_CR4","doi-asserted-by":"crossref","unstructured":"Clifford, R., Fontaine, A., Porat, E., Sach, B., Starikovskaya, T.: Dictionary matching in a stream. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 8737, pp. ??\u2013?? Springer, Heidelberg (2015)","DOI":"10.1007\/978-3-662-48350-3_31"},{"issue":"3","key":"45_CR5","doi-asserted-by":"publisher","first-page":"651","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), 651\u2013675 (1991)","journal-title":"J. ACM"},{"issue":"1","key":"45_CR6","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1090\/S0002-9939-1965-0174934-9","volume":"16","author":"N.J. Fine","year":"1965","unstructured":"Fine, N.J., Wilf, H.S.: Uniqueness theorems for periodic functions. P. Am. Math. Soc.\u00a016(1), 109\u2013114 (1965)","journal-title":"P. Am. Math. Soc."},{"key":"45_CR7","doi-asserted-by":"crossref","unstructured":"Fischer, J., Gagie, T., Gawrychowski, P., Kociumaka, T.: Approximating LZ77 via small-space multiple-pattern matching. CoRR abs\/1504.06647 (2015)","DOI":"10.1007\/978-3-662-48350-3_45"},{"key":"45_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/978-3-319-19929-0_15","volume-title":"Combinatorial Pattern Matching","author":"J. Fischer","year":"2015","unstructured":"Fischer, J., I, T., K\u00f6ppl, D.: Lempel Ziv Computation in Small Space (LZ-CISS). In: Cicalese, F., Porat, E., Vaccaro, U. (eds.) CPM 2015. LNCS, vol.\u00a09133, pp. 172\u2013184. Springer, Heidelberg (2015)"},{"issue":"3","key":"45_CR9","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1016\/0022-0000(83)90002-8","volume":"26","author":"Z. Galil","year":"1983","unstructured":"Galil, Z., Seiferas, J.I.: Time-space-optimal string matching. J. Comput. Syst. Sci.\u00a026(3), 280\u2013294 (1983)","journal-title":"J. Comput. Syst. Sci."},{"key":"45_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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 (extended abstract). In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol.\u00a01097, pp. 392\u2013403. Springer, Heidelberg (1996)"},{"key":"45_CR11","first-page":"1","volume-title":"SDM 2001","author":"B. Gum","year":"2001","unstructured":"Gum, B., Lipton, R.J.: Cheaper by the dozen: Batched algorithms. In: Kumar, V., Grossman, R.L. (eds.) SDM 2001, pp. 1\u201311. SIAM, Philadelphia (2001)"},{"key":"45_CR12","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/j.tcs.2012.10.050","volume":"475","author":"W. Hon","year":"2013","unstructured":"Hon, W., Ku, T., Shah, R., Thankachan, S.V., Vitter, J.S.: Faster compressed dictionary matching. Theor. Comput. Sci.\u00a0475, 113\u2013119 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"45_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/978-3-642-38527-8_14","volume-title":"Experimental Algorithms","author":"J. K\u00e4rkk\u00e4inen","year":"2013","unstructured":"K\u00e4rkk\u00e4inen, J., Kempa, D., Puglisi, S.J.: Lightweight Lempel-Ziv parsing. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol.\u00a07933, pp. 139\u2013150. Springer, Heidelberg (2013)"},{"issue":"2","key":"45_CR14","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"R.M. Karp","year":"1987","unstructured":"Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM J. Res. Dev.\u00a031(2), 249\u2013260 (1987)","journal-title":"IBM J. Res. Dev."},{"key":"45_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1007\/978-3-662-44777-2_50","volume-title":"Algorithms - ESA 2014","author":"T. Kociumaka","year":"2014","unstructured":"Kociumaka, T., Starikovskaya, T., Vildh\u00f8j, H.W.: Sublinear space algorithms for the longest common substring problem. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol.\u00a08737, pp. 605\u2013617. Springer, Heidelberg (2014)"},{"issue":"2","key":"45_CR16","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1515\/gcc-2012-0016","volume":"4","author":"M. Lohrey","year":"2012","unstructured":"Lohrey, M.: Algorithmics on SLP-compressed strings: A survey. Groups Complexity Cryptology\u00a04(2), 241\u2013299 (2012)","journal-title":"Groups Complexity Cryptology"},{"key":"45_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/978-3-540-70575-8_8","volume-title":"Automata, Languages and Programming","author":"M. Ru\u017ei\u0107","year":"2008","unstructured":"Ru\u017ei\u0107, M.: Constructing efficient dictionaries in close to sorting time. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 84\u201395. Springer, Heidelberg (2008)"},{"issue":"3","key":"45_CR18","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"},{"issue":"3","key":"45_CR19","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"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2015"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48350-3_45","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T20:00:46Z","timestamp":1559246446000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48350-3_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662483497","9783662483503"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48350-3_45","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]}}}