{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T02:17:02Z","timestamp":1743041822414,"version":"3.40.3"},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319199283"},{"type":"electronic","value":"9783319199290"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-19929-0_17","type":"book-chapter","created":{"date-parts":[[2015,6,15]],"date-time":"2015-06-15T13:09:49Z","timestamp":1434373789000},"page":"196-206","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Encodings of Range Maximum-Sum Segment Queries and Applications"],"prefix":"10.1007","author":[{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Patrick K.","family":"Nicholson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,16]]},"reference":[{"key":"17_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"LATIN 2000: Theoretical Informatics","author":"MA Bender","year":"2000","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol. 1776, pp. 88\u201394. Springer, Heidelberg (2000)"},{"key":"17_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/11809678_28","volume-title":"Computing and Combinatorics","author":"F Bengtsson","year":"2006","unstructured":"Bengtsson, F., Chen, J.: Computing maximum-scoring segments in almost linear time. In: Chen, D.Z., Lee, D.T. (eds.) COCOON 2006. LNCS, vol. 4112, pp. 255\u2013264. Springer, Heidelberg (2006)"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"Bengtsson, F., Chen, J.: Computing maximum-scoring segments optimally. Technical report, Research Report, Lule\u00e5 University of Technology (2007)","DOI":"10.1007\/11809678_28"},{"key":"17_CR4","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M Blum","year":"1972","unstructured":"Blum, M., Floyd, R., Pratt, V., Rivest, R., Tarjan, R.: Time bounds for selection. J. Comput. Syst. Sci. 7, 448\u2013461 (1972)","journal-title":"J. Comput. Syst. Sci."},{"issue":"16","key":"17_CR5","doi-asserted-by":"publisher","first-page":"2043","DOI":"10.1016\/j.dam.2007.05.018","volume":"155","author":"KY Chen","year":"2007","unstructured":"Chen, K.Y., Chao, K.M.: On the range maximum-sum segment query problem. Discrete Appl. Math. 155(16), 2043\u20132052 (2007)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"17_CR6","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1109\/TCBB.2004.43","volume":"1","author":"M Cs\u00fcr\u00f6s","year":"2004","unstructured":"Cs\u00fcr\u00f6s, M.: Maximum-scoring segment sets. IEEE\/ACM Trans. Comput. Biol. Bioinform. 1(4), 139\u2013150 (2004)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"17_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/978-3-642-40273-9_5","volume-title":"Space-Efficient Data Structures, Streams, and Algorithms","author":"S Durocher","year":"2013","unstructured":"Durocher, S.: A simple linear-space data structure for constant-time range minimum query. In: Brodnik, A., L\u00f3pez-Ortiz, A., Raman, V., Viola, A. (eds.) Ianfest-66. LNCS, vol. 8066, pp. 48\u201360. Springer, Heidelberg (2013)"},{"key":"17_CR8","unstructured":"Fischer, J.: Data structures for efficient string algorithms. Ph.D. thesis, Ludwig-Maximilians-Universit\u00e4t M\u00fcnchen, October 2007"},{"issue":"2","key":"17_CR9","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1137\/090779759","volume":"40","author":"J Fischer","year":"2011","unstructured":"Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput. 40(2), 465\u2013492 (2011)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"17_CR10","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.tcs.2006.09.014","volume":"368","author":"RF Geary","year":"2006","unstructured":"Geary, R.F., Rahman, N., Raman, R., Raman, V.: A simple optimal representation for balanced parentheses. Theor. Comput. Sci. 368(3), 231\u2013246 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science, FOCS 1989, pp. 549\u2013554. IEEE Computer Society, Washington, DC (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"issue":"1\u20133","key":"17_CR12","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1016\/j.tcs.2008.06.052","volume":"407","author":"HF Liu","year":"2008","unstructured":"Liu, H.F., Chao, K.M.: Algorithms for finding the weight-constrained $$k$$ longest paths in a tree and the length-constrained $$k$$ maximum-sum segments of a sequence. Theor. Comput. Sci. 407(1\u20133), 349\u2013358 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"17_CR13","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/S0097539799364092","volume":"31","author":"JI Munro","year":"2001","unstructured":"Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Comput. 31(3), 762\u2013776 (2001)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"17_CR14","first-page":"52","volume":"46","author":"G Navarro","year":"2013","unstructured":"Navarro, G.: Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences. ACM Comput. Surv. 46(4), 52 (2013)","journal-title":"ACM Comput. Surv."},{"key":"17_CR15","unstructured":"Nicholson, P.K., Gawrychowski, P.: Encodings of range maximum-sum segment queries and applications. CoRR abs\/1410.2847 (2014). http:\/\/arxiv.org\/abs\/1410.2847"},{"key":"17_CR16","unstructured":"Raman, R.: Personal communication"},{"key":"17_CR17","unstructured":"Ruzzo, W.L., Tompa, M.: A linear time algorithm for finding all maximal scoring subsequences. In: Proceedings of the Seventh International Conference on Intelligent Systems for Molecular Biology, pp. 234\u2013241. AAAI Press (1999)"},{"key":"17_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/978-3-642-40273-9_21","volume-title":"Space-Efficient Data Structures, Streams, and Algorithms","author":"M Skala","year":"2013","unstructured":"Skala, M.: Array range queries. In: Brodnik, A., L\u00f3pez-Ortiz, A., Raman, V., Viola, A. (eds.) Ianfest-66. LNCS, vol. 8066, pp. 333\u2013350. Springer, Heidelberg (2013)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19929-0_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T01:30:45Z","timestamp":1676943045000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-19929-0_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319199283","9783319199290"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19929-0_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"16 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}