{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T20:21:42Z","timestamp":1725740502672},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642401039"},{"type":"electronic","value":"9783642401046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40104-6_13","type":"book-chapter","created":{"date-parts":[[2013,7,11]],"date-time":"2013-07-11T05:36:30Z","timestamp":1373520990000},"page":"146-157","source":"Crossref","is-referenced-by-count":2,"title":["Fingerprints in Compressed Strings"],"prefix":"10.1007","author":[{"given":"Philip","family":"Bille","sequence":"first","affiliation":[]},{"given":"Patrick Hagge","family":"Cording","sequence":"additional","affiliation":[]},{"given":"Inge Li","family":"G\u00f8rtz","sequence":"additional","affiliation":[]},{"given":"Benjamin","family":"Sach","sequence":"additional","affiliation":[]},{"given":"Hjalte Wedel","family":"Vildh\u00f8j","sequence":"additional","affiliation":[]},{"given":"S\u00f8ren","family":"Vind","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"13_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/3-540-45022-X_8","volume-title":"Automata, Languages and Programming","author":"S. Alstrup","year":"2000","unstructured":"Alstrup, S., Holm, J.: Improved algorithms for finding level ancestors in dynamic trees. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 73\u201384. Springer, Heidelberg (2000)"},{"key":"13_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/3-540-56024-6_21","volume-title":"Combinatorial Pattern Matching","author":"A. Amir","year":"1992","unstructured":"Amir, A., Farach, M., Matias, Y.: Efficient randomized dictionary matching algorithms. In: Apostolico, A., Galil, Z., Manber, U., Crochemore, M. (eds.) CPM 1992. LNCS, vol.\u00a0644, pp. 262\u2013275. Springer, Heidelberg (1992)"},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"Andoni, A., Indyk, P.: Efficient algorithms for substring near neighbor problem. In: Proc. 17th SODA, pp. 1203\u20131212 (2006)","DOI":"10.1145\/1109557.1109690"},{"key":"13_CR4","unstructured":"Belazzougui, D., Boldi, P., Vigna, S.: Predecessor search with distance-sensitive query time. arXiv:1209.5441 (2012)"},{"key":"13_CR5","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/j.tcs.2003.05.002","volume":"321","author":"M. Bender","year":"2004","unstructured":"Bender, M., Farach-Colton, M.: The level ancestor problem simplified. Theoret. Comput. Sci.\u00a0321, 5\u201312 (2004)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"13_CR6","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/S0022-0000(05)80002-9","volume":"48","author":"O. Berkman","year":"1994","unstructured":"Berkman, O., Vishkin, U.: Finding level-ancestors in trees. J. Comput. System Sci.\u00a048(2), 214\u2013230 (1994)","journal-title":"J. Comput. System Sci."},{"key":"13_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/978-3-642-31265-6_24","volume-title":"Combinatorial Pattern Matching","author":"P. Bille","year":"2012","unstructured":"Bille, P., G\u00f8rtz, I.L., Sach, B., Vildh\u00f8j, H.W.: Time-space trade-offs for longest common extensions. In: K\u00e4rkk\u00e4inen, J., Stoye, J. (eds.) CPM 2012. LNCS, vol.\u00a07354, pp. 293\u2013305. Springer, Heidelberg (2012)"},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"Bille, P., Landau, G., Raman, R., Sadakane, K., Satti, S., Weimann, O.: Random access to grammar-compressed strings. In: Proc. 22nd SODA, pp. 373\u2013389 (2011)","DOI":"10.1137\/1.9781611973082.30"},{"issue":"7","key":"13_CR9","doi-asserted-by":"publisher","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","volume":"51","author":"M. Charikar","year":"2005","unstructured":"Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Sahai, A., Shelat, A.: The smallest grammar problem. IEEE Trans. Inf. Theory\u00a051(7), 2554\u20132576 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"13_CR10","doi-asserted-by":"crossref","first-page":"313","DOI":"10.3233\/FI-2011-565","volume":"111","author":"F. Claude","year":"2011","unstructured":"Claude, F., Navarro, G.: Self-indexed grammar-based compression. Fundamenta Informaticae\u00a0111(3), 313\u2013337 (2011)","journal-title":"Fundamenta Informaticae"},{"issue":"1","key":"13_CR11","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1137\/S0097539701424465","volume":"33","author":"R. Cole","year":"2003","unstructured":"Cole, R., Hariharan, R.: Faster suffix tree construction with missing suffix links. SIAM J. Comput.\u00a033(1), 26\u201342 (2003)","journal-title":"SIAM J. Comput."},{"key":"13_CR12","unstructured":"Cormode, G., Muthukrishnan, S.: Substring compression problems. In: Proc. 16th SODA, pp. 321\u2013330 (2005)"},{"issue":"1","key":"13_CR13","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1186810.1186812","volume":"3","author":"G. Cormode","year":"2007","unstructured":"Cormode, G., Muthukrishnan, S.: The string edit distance matching problem with moves. ACM Trans. Algorithms\u00a03(1), 2 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"13_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/BFb0028247","volume-title":"Algorithms and Data Structures","author":"P.F. Dietz","year":"1991","unstructured":"Dietz, P.F.: Finding level-ancestors in dynamic trees. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1991. LNCS, vol.\u00a0519, pp. 32\u201340. Springer, Heidelberg (1991)"},{"issue":"4","key":"13_CR15","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\u2013Ziv compressed strings. Algorithmica\u00a020(4), 388\u2013404 (1998)","journal-title":"Algorithmica"},{"key":"13_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/3-540-61258-0_3","volume-title":"Combinatorial Pattern Matching","author":"L. G\u0105sieniec","year":"1996","unstructured":"G\u0105sieniec, L., Karpinski, M., Plandowski, W., Rytter, W.: Randomized efficient algorithms for compressed strings: The finger-print approach. In: Hirschberg, D.S., Meyers, G. (eds.) CPM 1996. LNCS, vol.\u00a01075, pp. 39\u201349. Springer, Heidelberg (1996)"},{"key":"13_CR17","unstructured":"G\u0105sieniec, L., Kolpakov, R., Potapov, I., Sant, P.: Real-time traversal in grammar-based compressed files. In: Proc. 15th DCC, p. 458 (2005)"},{"issue":"2","key":"13_CR18","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput.\u00a013(2), 338\u2013355 (1984)","journal-title":"SIAM J. Comput."},{"key":"13_CR19","unstructured":"Kalai, A.: Efficient pattern-matching with don\u2019t cares. In: Proc. 13th SODA, pp. 655\u2013656 (2002)"},{"issue":"2","key":"13_CR20","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."},{"issue":"4","key":"13_CR21","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0020-0190(90)90022-P","volume":"35","author":"K. Mehlhorn","year":"1990","unstructured":"Mehlhorn, K., N\u00e4her, S.: Bounded ordered dictionaries in O(loglogN) time and O(n) space. Inform. Process. Lett.\u00a035(4), 183\u2013189 (1990)","journal-title":"Inform. Process. Lett."},{"key":"13_CR22","doi-asserted-by":"crossref","unstructured":"Porat, B., Porat, E.: Exact and approximate pattern matching in the streaming model. In: Proc. 50th FOCS, pp. 315\u2013323 (2009)","DOI":"10.1109\/FOCS.2009.11"},{"issue":"1","key":"13_CR23","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0304-3975(02)00777-6","volume":"302","author":"W. Rytter","year":"2003","unstructured":"Rytter, W.: Application of Lempel\u2013Ziv factorization to the approximation of grammar-based compression. Theoret. Comput. Sci.\u00a0302(1), 211\u2013222 (2003)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"13_CR24","first-page":"99","volume":"10","author":"P. Emde Boas van","year":"1976","unstructured":"van Emde Boas, P., Kaas, R., Zijlstra, E.: Design and implementation of an efficient priority queue. Theory Comput. Syst.\u00a010(1), 99\u2013127 (1976)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"13_CR25","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"D. Willard","year":"1983","unstructured":"Willard, D.: Log-logarithmic worst-case range queries are possible in space \u0398(N). Inform. Process. Lett.\u00a017(2), 81\u201384 (1983)","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"13_CR26","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. Inf. Theory\u00a023(3), 337\u2013343 (1977)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"5","key":"13_CR27","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. Inf. Theory\u00a024(5), 530\u2013536 (1978)","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40104-6_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,30]],"date-time":"2020-07-30T11:15:52Z","timestamp":1596107752000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40104-6_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642401039","9783642401046"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40104-6_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}