{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:10:03Z","timestamp":1763467803790},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540438649"},{"type":"electronic","value":"9783540454656"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45465-9_62","type":"book-chapter","created":{"date-parts":[[2007,5,27]],"date-time":"2007-05-27T01:12:57Z","timestamp":1180228377000},"page":"728-739","source":"Crossref","is-referenced-by-count":8,"title":["Solving the String Statistics Problem in Time $$ \\mathcal{O} $$ (nlogn)"],"prefix":"10.1007","author":[{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rune B.","family":"Lyngs\u00f8","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anna","family":"\u00d6stlin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian N. S.","family":"Pedersen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,6,25]]},"reference":[{"key":"62_CR1","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0304-3975(93)90159-Q","volume":"119","author":"A. Apostolico","year":"1993","unstructured":"A. Apostolico and A. Ehrenfeucht. Efficient detection of quasiperiodicities in strings. Theoretical Computer Science, 119:247\u2013265, 1993.","journal-title":"Theoretical Computer Science"},{"key":"62_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":"62_CR3","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/BF01955046","volume":"15","author":"A. Apostolico","year":"1996","unstructured":"A. Apostolico and F. P. Preparata. Data structures and algorithms for the string statistics problem. Algorithmica, 15:481\u2013494, 1996.","journal-title":"Algorithmica"},{"issue":"1","key":"62_CR4","first-page":"77","volume":"1","author":"G. S. Brodal","year":"2000","unstructured":"G. S. Brodal, R. Lyngs\u00f8, C. N. S. Pedersen, and J. Stoye. Finding maximal pairs with bounded gap. Journal of Discrete Algorithms, Special Issue of Matching Patterns, 1(1):77\u2013104, 2000.","journal-title":"Journal of Discrete Algorithms, Special Issue of Matching Patterns"},{"key":"62_CR5","doi-asserted-by":"crossref","unstructured":"G. S. Brodal, R. B. Lyngs\u00f8, A. Ostlin, and C. N. S. Pedersen. Solving the string statistics problem in time O(n log n). Technical Report RS-02-13, BRICS, Department of Computer Science, University of Aarhus, 2002.","DOI":"10.7146\/brics.v9i13.21731"},{"key":"62_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1007\/3-540-45123-4_33","volume-title":"Proc. 11th Combinatorial Pattern Matching","author":"G. S. Brodal","year":"2000","unstructured":"G. S. Brodal and C. N. S. Pedersen. Finding maximal quasiperiodicities in strings. In Proc. 11th Combinatorial Pattern Matching, volume 1848 of Lecture Notes in Computer Science, pages 397\u2013411. Springer Verlag, Berlin, 2000."},{"issue":"2","key":"62_CR7","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"},{"key":"62_CR8","doi-asserted-by":"crossref","unstructured":"M. Farach. Optimal suffix tree construction with large alphabets. In Proc. 38th Ann. Symp. on Foundations of Computer Science (FOCS), pages 137\u2013143, 1997.","DOI":"10.1109\/SFCS.1997.646102"},{"issue":"1","key":"62_CR9","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1006\/jcta.1997.2843","volume":"82","author":"A. S. Fraenkel","year":"1998","unstructured":"A. S. Fraenkel and J. Simpson. How many squares can a string contain? Journal of Combinatorial Theory, Series A, 82(1):112\u2013120, 1998.","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"62_CR10","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"},{"issue":"1\u20133","key":"62_CR11","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1016\/S0019-9958(86)80033-X","volume":"86","author":"K. Hoffmann","year":"1986","unstructured":"K. Hoffmann, K. Mehlhorn, P. Rosenstiehl, and R. E. Tarjan. Sorting Jordan sequences in linear time using level-linked search trees. Information and Control, 86(1\u20133):170\u2013184, 1986.","journal-title":"Information and Control"},{"key":"62_CR12","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":"62_CR13","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 of Computing, 1(1):31\u201339, 1972.","journal-title":"SIAM Journal of Computing"},{"key":"62_CR14","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D. E. Knuth","year":"1977","unstructured":"D. E. Knuth, J. H. Morris, and V. R. Pratt. Fast pattern matching in strings. SIAM Journal of Computing, 6:323\u2013350, 1977.","journal-title":"SIAM Journal of Computing"},{"issue":"2","key":"62_CR15","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 suffix tree construction algorithm. Journal of the ACM, 23(2):262\u2013272, 1976.","journal-title":"Journal of the ACM"},{"key":"62_CR16","series-title":"Data Structures and Algorithms","volume-title":"Sorting and Searching","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn. Sorting and Searching, volume 1 of Data Structures and Algorithms. Springer Verlag, Berlin, 1984."},{"key":"62_CR17","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1016\/S0304-3975(01)00121-9","volume":"270","author":"J. Stoye","year":"2002","unstructured":"J. Stoye and D. Gusfield. Simple and flexible detection of contiguous repeats using a suffix tree. Theoretical Computer Science, 270:843\u2013856, 2002.","journal-title":"Theoretical Computer Science"},{"key":"62_CR18","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 suffix trees. Algorithmica, 14:249\u2013260, 1995.","journal-title":"Algorithmica"},{"key":"62_CR19","doi-asserted-by":"crossref","unstructured":"P. Weiner. Linear pattern matching algorithms. In Proc. 14th Symposium on Switching and Automata Theory, pages 1\u201311, 1973.","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45465-9_62","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T11:05:29Z","timestamp":1556449529000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45465-9_62"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540438649","9783540454656"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-45465-9_62","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}