{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T21:21:47Z","timestamp":1725571307021},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642175138"},{"type":"electronic","value":"9783642175145"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"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":[[2010]]},"DOI":"10.1007\/978-3-642-17514-5_29","type":"book-chapter","created":{"date-parts":[[2010,12,3]],"date-time":"2010-12-03T15:09:23Z","timestamp":1291388963000},"page":"339-350","source":"Crossref","is-referenced-by-count":1,"title":["Identifying Approximate Palindromes in Run-Length Encoded Strings"],"prefix":"10.1007","author":[{"given":"Kuan-Yu","family":"Chen","sequence":"first","affiliation":[]},{"given":"Ping-Hui","family":"Hsu","sequence":"additional","affiliation":[]},{"given":"Kun-Mao","family":"Chao","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"29_CR1","doi-asserted-by":"crossref","unstructured":"Amir, A., Benson, G.: Efficient Two-Dimensional Compressed Matching. In: Data Compression Conference, pp. 279\u2013288 (1992)","DOI":"10.1109\/DCC.1992.227453"},{"issue":"1","key":"29_CR2","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1006\/jcom.1998.0493","volume":"15","author":"A. Apostolico","year":"1999","unstructured":"Apostolico, A., Landau, G.M., Skiena, S.: Matching for Run-Length Encoded Strings. Journal of Complexity\u00a015(1), 4\u201316 (1999)","journal-title":"Journal of Complexity"},{"key":"29_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M. Berg de","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications. Springer, Heidelberg (2008)"},{"key":"29_CR4","unstructured":"Bentley, J.L.: Solutions to Klee\u2019s Rectangle Problems. Technical Report, Carnegie-Mellon University, Pittsburgh, PA (1977)"},{"key":"29_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/978-3-642-15775-2_36","volume-title":"Algorithms \u2013 ESA 2010","author":"K.-Y. Chen","year":"2010","unstructured":"Chen, K.-Y., Chao, K.-M.: A Fully Compressed Algorithm for Computing the Edit Distance of Run-Length Encoded Strings. In: de Berg, M., Meyer, U. (eds.) ESA 2010. LNCS, vol.\u00a06346, pp. 415\u2013426. Springer, Heidelberg (2010)"},{"key":"29_CR6","doi-asserted-by":"crossref","unstructured":"Chen, K.-Y., Hsu, P.-H., Chao, K.-M.: Hardness of Comparing Two Run-Length Encoded Strings. Journal of Complexity (accepted) (A preliminary version appeared in CPM 2009)","DOI":"10.1016\/j.jco.2010.03.003"},{"issue":"4","key":"29_CR7","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1038\/ng0410-279","volume":"42","author":"S.J. Diede","year":"2010","unstructured":"Diede, S.J., Tanaka, H., Bergstrom, D.A., Yao, M.-C., Tapscott, S.J.: Tapscott: Genome-wide Analysis of Palindrome Formation. Nature Genetics\u00a042(4), 279 (2010)","journal-title":"Nature Genetics"},{"issue":"6","key":"29_CR8","doi-asserted-by":"publisher","first-page":"987","DOI":"10.1145\/355541.355547","volume":"47","author":"M. Farach-Colton","year":"2000","unstructured":"Farach-Colton, M., Ferragina, P., Muthukrishnan, S.: On the Sorting-Complexity of Suffix Tree Construction. Journal of ACM\u00a047(6), 987\u20131011 (2000)","journal-title":"Journal of ACM"},{"key":"29_CR9","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":"29_CR10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology","author":"D. Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)"},{"issue":"2","key":"29_CR11","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 Journal on Computing\u00a013(2), 338\u2013355 (1984)","journal-title":"SIAM Journal on Computing"},{"key":"29_CR12","unstructured":"Hermelin, D., Landau, G.M., Landau, S., Weimann, O.: A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression. In: STACS, pp. 529\u2013540 (2009)"},{"key":"29_CR13","doi-asserted-by":"crossref","unstructured":"Hsu, P.-H., Chen, K.-Y., Chao, K.-M.: Finding All Approximate Gapped Palindromes. In: ISAAC, pp. 1084\u20131093 (2009)","DOI":"10.1007\/978-3-642-10631-6_109"},{"issue":"38-40","key":"29_CR14","doi-asserted-by":"publisher","first-page":"3942","DOI":"10.1016\/j.tcs.2009.05.032","volume":"410","author":"J.J. Liu","year":"2009","unstructured":"Liu, J.J., Huang, G.S., Wang, Y.L.: A Fast Algorithm for Finding the Positions of All Squares in a Run-Length Encoded String. Theoretical Computer Science\u00a0410(38-40), 3942\u20133948 (2009)","journal-title":"Theoretical Computer Science"},{"key":"29_CR15","doi-asserted-by":"crossref","unstructured":"Lueker, G.S.: A Data Structure for Orthogonal Range Queries. In: FOCS, pp. 28\u201334 (1978)","DOI":"10.1109\/SFCS.1978.1"},{"issue":"8-10","key":"29_CR16","doi-asserted-by":"publisher","first-page":"900","DOI":"10.1016\/j.tcs.2008.12.016","volume":"410","author":"W. Matsubara","year":"2009","unstructured":"Matsubara, W., Inenaga, S., Ishino, A., Shinohara, A., Nakamura, T., Hashimoto, K.: Efficient Algorithms to Compute Compressed Longest Common Substrings and Compressed Palindromes. Theoretical Computer Science\u00a0410(8-10), 900\u2013913 (2009)","journal-title":"Theoretical Computer Science"},{"key":"29_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/3-540-47849-3_3","volume-title":"SOFSEM\u201999: Theory and Practice of Informatics","author":"W. Rytter","year":"1999","unstructured":"Rytter, W.: Algorithms on Compressed Strings and Arrays. In: Bartosek, M., Tel, G., Pavelka, J. (eds.) SOFSEM 1999. LNCS, vol.\u00a01725, pp. 48\u201365. Springer, Heidelberg (1999)"},{"key":"29_CR18","volume-title":"Predicate-Oriented Database Search Algorithms","author":"D.E. Willard","year":"1978","unstructured":"Willard, D.E.: Predicate-Oriented Database Search Algorithms. Garland Publishing, New York (1978)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-17514-5_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,14]],"date-time":"2021-11-14T11:32:17Z","timestamp":1636889537000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17514-5_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642175138","9783642175145"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17514-5_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}