{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,28]],"date-time":"2026-09-28T22:54:08Z","timestamp":1790636048186,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540662785","type":"print"},{"value":"9783540484523","type":"electronic"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"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":[[1999]]},"DOI":"10.1007\/3-540-48452-3_11","type":"book-chapter","created":{"date-parts":[[2007,10,6]],"date-time":"2007-10-06T21:55:40Z","timestamp":1191707740000},"page":"134-149","source":"Crossref","is-referenced-by-count":17,"title":["Finding Maximal Pairs with Bounded Gap"],"prefix":"10.1007","author":[{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rune B.","family":"Lyngs\u00f8","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian N. S.","family":"Pedersen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jens","family":"Stoye","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[1999,7,8]]},"reference":[{"key":"11_CR1","first-page":"263","volume":"146","author":"G.M. Adelson-Velskii","year":"1962","unstructured":"G.M. Adel\u2019son-Vel\u2019skii and Y.M. Landis. An algorithm for the organization of information. Doklady Akademii Nauk SSSR, 146:263\u2013266, 1962. English translation in Soviet Math. Dokl., 3:1259-1262.","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0304-3975(83)90109-3","volume":"22","author":"A. Apostolico","year":"1983","unstructured":"A. Apostolico and F.P. Preparata. Optimal off-line detection of repetitions in a string. Theoretical Computer Science, 22:297\u2013315, 1983.","journal-title":"Theoretical Computer Science"},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"G.S. Brodal, R.B. Lyngs\u00f8, C.N.S. Pedersen, and J. Stoye. Finding maximal pairs with bounded gap. Technical Report RS-99-12, BRICS, April 1999.","DOI":"10.7146\/brics.v6i12.20069"},{"issue":"2","key":"11_CR4","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1145\/322123.322127","volume":"26","author":"M.R. Brown","year":"1979","unstructured":"M.R. Brown and R.E. Tarjan. A fast merging algorithm. Journal of the ACM, 26(2):211\u2013226, 1979.","journal-title":"Journal of the ACM"},{"issue":"5","key":"11_CR5","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0020-0190(81)90024-7","volume":"12","author":"M. Crochemore","year":"1981","unstructured":"M. Crochemore. An optimal algorithm for computing the repetitions in a word. Information Processing Letters, 12(5):244\u2013250, 1981.","journal-title":"Information Processing Letters"},{"key":"11_CR6","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0304-3975(86)90041-1","volume":"45","author":"M. Crochemore","year":"1986","unstructured":"M. Crochemore. Tranducers and repetitions. Theoretical Computer Science, 45:63\u201386, 1986.","journal-title":"Theoretical Computer Science"},{"key":"11_CR7","doi-asserted-by":"crossref","unstructured":"M. Farach. Optimal sufix tree construction with large alphabets. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), pages 137\u2013143, 1997.","DOI":"10.1109\/SFCS.1997.646102"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"L.J. Guibas and R. Sedgewick. A dichromatic framework for balanced trees. In Proceedings of the 19th Annual Symposium on Foundations of Computer Science (FOCS), pages 8\u201321, 1978.","DOI":"10.1109\/SFCS.1978.3"},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"D. Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997.","DOI":"10.1017\/CBO9780511574931"},{"key":"11_CR10","unstructured":"D. Gusfield and J. Stoye. Linear time algorithms for_nding and representing all the tandem repeats in a string. Technical Report CSE-98-4, Department of Computer Science, UC Davis, 1998."},{"key":"11_CR11","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF00288968","volume":"17","author":"S. Huddleston","year":"1982","unstructured":"S. Huddleston and K. Mehlhorn. A new data structure for representing sorted lists. Acta Informatica, 17:157\u2013184, 1982.","journal-title":"Acta Informatica"},{"issue":"1","key":"11_CR12","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1137\/0201004","volume":"1","author":"F.K. Hwang","year":"1972","unstructured":"F.K. Hwang and S. Lin. A simple algorithm for merging two disjoint linearly ordered sets. SIAM Journal on Computing, 1(1):31\u201339, 1972.","journal-title":"SIAM Journal on Computing"},{"key":"11_CR13","first-page":"841","volume":"85","author":"S. Karlin","year":"1988","unstructured":"S. Karlin, M. Morris, G. Ghandour, and M.-Y. Leung. Efficient algorithms for molecular sequence analysis. Proceedings of the National Academy of Science, USA, 85:841\u2013845, 1988.","journal-title":"Efficient algorithms for molecular sequence analysis"},{"key":"11_CR14","unstructured":"R. Kolpakov and G. Kucherov. Maximal repetitions in words or how to find all squares in linear time. Technical Report 98-R-227, LORIA, 1998."},{"key":"11_CR15","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1007\/3-540-58094-8_13","volume-title":"Computation of squares in a string","author":"S.R. Kosaraju","year":"1994","unstructured":"S.R. Kosaraju. Computation of squares in a string. In Proceedings of the 5th Annual Symposium on Combinatorial Pattern Matching (CPM), volume 807 of Lecture Notes in Computer Science, pages 146\u2013150, 1994."},{"key":"11_CR16","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1007\/BFb0029801","volume-title":"An algorithm for approximate tandem repeats","author":"G.M. Landau","year":"1993","unstructured":"G.M. Landau and J.P. Schmidt. An algorithm for approximate tandem repeats. In Proceedings of the 4th Annual Symposium on Combinatorial Pattern Matching (CPM), volume 684 of Lecture Notes in Computer Science, pages 120\u2013133, 1993."},{"key":"11_CR17","doi-asserted-by":"publisher","first-page":"1367","DOI":"10.1016\/0022-2836(91)90938-3","volume":"221","author":"M.-Y. Leung","year":"1991","unstructured":"M.-Y. Leung, B.E. Blaisdell, C. Burge, and S. Karlin. An efficient algorithm for identifying matches with errors in multiple long molecular sequences. Journal of Molecular Biology, 221:1367\u20131378, 1991.","journal-title":"Journal of Molecular Biology"},{"key":"11_CR18","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1016\/0196-6774(84)90021-X","volume":"5","author":"M.G. Main","year":"1984","unstructured":"M.G. Main and R.J. Lorentz. An O(n log n) algorithm for finding all repetitions in a string. Journal of Algorithms, 5:422\u2013432, 1984.","journal-title":"Journal of Algorithms"},{"key":"11_CR19","series-title":"NATO ASI Series","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/978-3-642-82456-2_18","volume-title":"Combinatorial Algorithms on Words","author":"M.G. Main","year":"1985","unstructured":"M.G. Main and R.J. Lorentz. Linear time recognition of squarefree strings. In A. Apostolico and Z. Galil, editors, Combinatorial Algorithms on Words, volume F12 of NATO ASI Series, pages 271\u2013278. Springer, Berlin, 1985."},{"issue":"2","key":"11_CR20","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"E.M. McCreight","year":"1976","unstructured":"E.M. McCreight. A space-economical sufix tree construction algorithm. Journal of the ACM, 23(2):262\u2013272, 1976.","journal-title":"Journal of the ACM"},{"key":"11_CR21","unstructured":"K. Mehlhorn. Sorting and Searching, volume 1 of Data Structures and Algorithms. Springer-Verlag, 1994."},{"key":"11_CR22","unstructured":"K. Mehlhorn and S. N\u00e4her. The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press, 1999. To appear. See http:\/\/www.mpisb.mpg.de\/_mehlhorn\/LEDAbook.html ."},{"key":"11_CR23","doi-asserted-by":"crossref","unstructured":"M.-F. Sagot and E.W. Myers. Identifying satellites in nucleic acid sequences. In Proceedings of the 2nd Annual International Conference on Computational Molecular Biology (RECOMB), pages 234\u2013242, 1998.","DOI":"10.1145\/279069.279120"},{"key":"11_CR24","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1007\/BFb0030787","volume-title":"Simple and flexible detection of contiguous repeats using a sufix tree","author":"J. Stoye","year":"1998","unstructured":"J. Stoye and D. Gusfield. Simple and flexible detection of contiguous repeats using a sufix tree. In Proceedings of the 9th Annual Symposium on Combinatorial Pattern Matching (CPM), volume 1448 of Lecture Notes in Computer Science, pages 140\u2013152, 1998."},{"key":"11_CR25","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01206331","volume":"14","author":"E. Ukkonen","year":"1995","unstructured":"E. Ukkonen. On-line construction of sufix trees. Algorithmica, 14:249\u2013260, 1995.","journal-title":"Algorithmica"},{"key":"11_CR26","doi-asserted-by":"crossref","unstructured":"P. Weiner. Linear pattern matching algorithms. In Proceedings of the 14th Symposium on Switching and Automata Theory, pages 1\u201311, 1973.","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48452-3_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T11:42:21Z","timestamp":1556883741000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48452-3_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662785","9783540484523"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-48452-3_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999]]}}}