{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T21:25:40Z","timestamp":1776288340193,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540354550","type":"print"},{"value":"9783540354611","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11780441_5","type":"book-chapter","created":{"date-parts":[[2006,6,30]],"date-time":"2006-06-30T11:02:51Z","timestamp":1151665371000},"page":"36-48","source":"Crossref","is-referenced-by-count":84,"title":["Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE"],"prefix":"10.1007","author":[{"given":"Johannes","family":"Fischer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Volker","family":"Heun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1137\/0205011","volume":"5","author":"A.V. Aho","year":"1976","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: On finding lowest common ancestors in trees. SIAM J. Comput.\u00a05, 115\u2013132 (1976)","journal-title":"SIAM J. Comput."},{"key":"5_CR2","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, 338\u2013355 (1984)","journal-title":"SIAM J. Comput."},{"key":"5_CR3","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1137\/0217079","volume":"17","author":"B. Schieber","year":"1988","unstructured":"Schieber, B., Vishkin, U.: On finding lowest common ancestors: Simplification and parallelization. SIAM J. Comput.\u00a017, 1253\u20131262 (1988)","journal-title":"SIAM J. Comput."},{"key":"5_CR4","doi-asserted-by":"crossref","unstructured":"Berkman, O., Vishkin, U.: Recursive star-tree parallel data structure. SIAM J. Comput.\u00a022 (1993)","DOI":"10.1137\/0222017"},{"key":"5_CR5","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":"M.A. 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.\u00a01776, pp. 88\u201394. Springer, Heidelberg (2000)"},{"key":"5_CR6","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.jalgor.2005.08.001","volume":"57","author":"M.A. Bender","year":"2005","unstructured":"Bender, M.A., Farach-Colton, M., Pemmasani, G., Skiena, S., Sumazin, P.: Lowest common ancestors in trees and directed acyclic graphs. J. Algorithms\u00a057, 75\u201394 (2005)","journal-title":"J. Algorithms"},{"key":"5_CR7","first-page":"135","volume-title":"Proc. of the ACM STOC","author":"H.N. Gabow","year":"1984","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proc. of the ACM STOC, pp. 135\u2013143. ACM Press, New York (1984)"},{"key":"5_CR8","first-page":"66","volume-title":"Information Retrieval: Data Structures and Algorithms","author":"G.H. Gonnet","year":"1992","unstructured":"Gonnet, G.H., Baeza-Yates, R.A., Snider, T.: New indices for text: PAT trees and PAT arrays. In: Frakes, W.B., Baeza-Yates, R.A. (eds.) Information Retrieval: Data Structures and Algorithms, pp. 66\u201382. Prentice-Hall, Englewood Cliffs (1992)"},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U. Manber","year":"1993","unstructured":"Manber, U., Myers, E.W.: Suffix arrays: A new method for on-line string searches. SIAM J. Comput.\u00a022, 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"key":"5_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/3-540-48194-X_17","volume-title":"Combinatorial Pattern Matching","author":"T. Kasai","year":"2001","unstructured":"Kasai, T., Lee, G., Arimura, H., Arikawa, S., Park, K.: Linear-time longest-common-prefix computation in suffix arrays and its applications. In: Amir, A., Landau, G.M. (eds.) CPM 2001. LNCS, vol.\u00a02089, pp. 181\u2013192. Springer, Heidelberg (2001)"},{"key":"5_CR11","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S1570-8667(03)00065-0","volume":"2","author":"M.I. Abouelhoda","year":"2004","unstructured":"Abouelhoda, M.I., Kurtz, S., Ohlebusch, E.: Replacing suffix trees with enhanced suffix arrays. J. Discrete Algorithms\u00a02, 53\u201386 (2004)","journal-title":"J. Discrete Algorithms"},{"key":"5_CR12","first-page":"258","volume-title":"Proc. SPAA","author":"S. Alstrup","year":"2002","unstructured":"Alstrup, S., Gavoille, C., Kaplan, H., Rauhe, T.: Nearest common ancestors: A survey and a new distributed algorithm. In: Proc. SPAA, pp. 258\u2013264. ACM Press, New York (2002)"},{"key":"5_CR13","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1145\/358841.358852","volume":"23","author":"J. Vuillemin","year":"1980","unstructured":"Vuillemin, J.: A unifying look at data structures. Comm. ACM\u00a023, 229\u2013239 (1980)","journal-title":"Comm. ACM"},{"key":"5_CR14","doi-asserted-by":"publisher","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"R.E. Tarjan","year":"1985","unstructured":"Tarjan, R.E., Vishkin, U.: An efficient parallel biconnectivity algorithm. SIAM J. Comput.\u00a014, 862\u2013874 (1985)","journal-title":"SIAM J. Comput."},{"key":"5_CR15","first-page":"487","volume":"194","author":"V.L. Arlazarov","year":"1970","unstructured":"Arlazarov, V.L., Dinic, E.A., Kronrod, M.A., Faradzev, I.A.: On economic construction of the transitive closure of a directed graph. Dokl. Acad. Nauk. SSSR\u00a0194, 487\u2013488 (1970) (in Russian), Engl. transl. in Soviet Math. Dokl. 11, 1209\u20131210 (1975)","journal-title":"Dokl. Acad. Nauk. SSSR"},{"key":"5_CR16","series-title":"Generating All Trees; History of Combinatorial Generation","volume-title":"The Art of Computer Programming","author":"D.E. Knuth","year":"2006","unstructured":"Knuth, D.E.: The Art of Computer Programming. Generating All Trees; History of Combinatorial Generation, vol.\u00a04, fasc.\u00a04. Addison-Wesley, Reading (2006)"},{"key":"5_CR17","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1016\/0196-6774(84)90021-X","volume":"5","author":"M.G. Main","year":"1984","unstructured":"Main, M.G., Lorentz, R.J.: An O(n logn) algorithm for finding all repetitions in a string. J. Algorithms\u00a05, 422\u2013432 (1984)","journal-title":"J. Algorithms"},{"key":"5_CR18","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1016\/j.jcss.2004.03.004","volume":"69","author":"D. Gusfield","year":"2004","unstructured":"Gusfield, D., Stoye, J.: Linear time algorithm for finding and representing all tandem repeats in a string. J. Comput. Syst. Sci.\u00a069, 525\u2013546 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"5_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1089\/106652701300099038","volume":"8","author":"G. Landau","year":"2001","unstructured":"Landau, G., Schmidt, J.P., Sokol, D.: An algorithm for approximate tandem repeats. J. Comput. Biol.\u00a08, 1\u201318 (2001)","journal-title":"J. Comput. Biol."},{"key":"5_CR20","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/BF01840446","volume":"1","author":"E.W. Myers","year":"1986","unstructured":"Myers, E.W.: An O(nd) difference algorithm and its variations. Algorithmica\u00a01, 251\u2013266 (1986)","journal-title":"Algorithmica"},{"key":"5_CR21","first-page":"220","volume-title":"Proc. STOC","author":"G. Landau","year":"1986","unstructured":"Landau, G., Vishkin, U.: Introducing efficient parallelism into approximate string matching and a new serial algorithm. In: Proc. STOC, pp. 220\u2013230. ACM Press, New York (1986)"},{"key":"5_CR22","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences","author":"D. Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences. Cambridge University Press, Cambridge (1997)"},{"key":"5_CR23","first-page":"77","volume-title":"Proc. ALENEX\/ANALCO","author":"K.B. Sch\u00fcrmann","year":"2005","unstructured":"Sch\u00fcrmann, K.B., Stoye, J.: An incomplex algorithm for fast suffix array construction. In: Proc. ALENEX\/ANALCO, pp. 77\u201385. SIAM Press, Philadelphia (2005)"},{"key":"5_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1007\/978-3-540-27810-8_32","volume-title":"Algorithm Theory - SWAT 2004","author":"G. Manzini","year":"2004","unstructured":"Manzini, G.: Two space saving tricks for linear time lcp array computation. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol.\u00a03111, pp. 372\u2013383. Springer, Heidelberg (2004)"},{"key":"5_CR25","unstructured":"Sadakane, K.: Succinct representations of lcp information and improvements in the compressed suffix arrays. In: Proc. SODA, pp. 225\u2013237. ACM\/SIAM (2002)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11780441_5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:16:22Z","timestamp":1619493382000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11780441_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540354550","9783540354611"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/11780441_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}