{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:24:07Z","timestamp":1725488647974},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540564133"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/3-540-47555-9_12","type":"book-chapter","created":{"date-parts":[[2007,8,8]],"date-time":"2007-08-08T23:23:49Z","timestamp":1186615429000},"page":"138-152","source":"Crossref","is-referenced-by-count":1,"title":["Suffix trees and string complexity"],"prefix":"10.1007","author":[{"given":"Luke","family":"O\u2019Connor","sequence":"first","affiliation":[]},{"given":"Tim","family":"Snider","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"12_CR1","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley Publishing Company, 1974."},{"key":"12_CR2","unstructured":"A. Apostolico and W. Szpankowski. Self-alignments in words and their applications. Technical Report CDS-TR-732, Purdue University, 1987."},{"issue":"3","key":"12_CR3","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1214\/aos\/1176350045","volume":"14","author":"R. Arratia","year":"1986","unstructured":"R. Arratia, L. Gordon, and M. Waterman. An extreme value theory for sequence matching. The Annals of Statistics, 14(3):971\u2013993, 1986.","journal-title":"The Annals of Statistics"},{"key":"12_CR4","unstructured":"H. Beker and F. Piper. Cipher Systems. Wiley, 1982."},{"key":"12_CR5","first-page":"12","volume":"21","author":"A. Blumer","year":"1983","unstructured":"A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler, and R McConnell. Linear size finite automata for the set of all subwords of a word: outline of results. Bulletin of the European Association of Theoretical Computer Science, 21:12\u201320, 1983.","journal-title":"Bulletin of the European Association of Theoretical Computer Science"},{"key":"12_CR6","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0166-218X(92)90270-K","volume":"24","author":"A. Blumer","year":"1989","unstructured":"A. Blumer, E. Ehrenfeucht, and D. Haussler. Average sizes of suffix trees and DAWGs. Discrete Applied Mathemetics, 24:37\u201345, 1989.","journal-title":"Discrete Applied Mathemetics"},{"issue":"4","key":"12_CR7","doi-asserted-by":"publisher","first-page":"822","DOI":"10.1109\/18.53741","volume":"IT-36","author":"A. Chan","year":"1990","unstructured":"A. Chan and R. Games. On the quadratic spans of periodic sequences. IEEE Transactions on Information Theory, IT-36(4):822\u2013829, 1990.","journal-title":"IEEE Transactions on Information Theory"},{"key":"12_CR8","first-page":"754","volume":"49","author":"N. G. Bruijn de","year":"1946","unstructured":"N. G. de Bruijn. A combinatorial problem. Nederl. Akad. Wetensch. Proc, 49:754\u2013758, 1946.","journal-title":"Nederl. Akad. Wetensch. Proc"},{"key":"12_CR9","unstructured":"D. E. R. Denning. Cryptography and Data Security. Addison-Wesley Publishing Company, 1982."},{"key":"12_CR10","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/BF00264248","volume":"21","author":"L. Devroye","year":"1984","unstructured":"L. Devroye. A probabilistic analysis of the height of tries and of the complexity if triesort. Acta Informatica, 21:229\u2013232, 1984.","journal-title":"Acta Informatica"},{"key":"12_CR11","unstructured":"S. Golumb. Shift Register Sequences. Aegean Park Press, 1982."},{"key":"12_CR12","unstructured":"G. H. Gonnet and R. Baeza-Yates. Handbook of Algorithms and Data Structures. Addison-Wesley, Second Edition, 1991."},{"issue":"3","key":"12_CR13","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1109\/TIT.1971.1054618","volume":"17","author":"E. J. Growth","year":"1971","unstructured":"E. J. Growth. Generation of binary sequences with controllable complexity. IEEE Transactions on Information Theory, 17(3):288\u2013296, 1971.","journal-title":"IEEE Transactions on Information Theory"},{"key":"12_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/BFb0030362","volume-title":"Advances in Cryptology, AUSTCRYPT 90","author":"H. Gustafson","year":"1990","unstructured":"H. Gustafson, E. Dawson, and W. Caellie. Comparison of block ciphers. Advances in Cryptology, AUSTCRYPT 90, Lecture Notes in Computer Science, vol. 453, J. Seberry and J. Piepryzk eds., Springer-Verlag, pages 208\u2013220, 1990."},{"key":"12_CR15","unstructured":"J. Hopcroft and J. Ullman. An introduction to automata, languages and computation. Addison-Wesley Publishing Company, 1979."},{"key":"12_CR16","unstructured":"P. Jacquet and W. Szpankowski. Autocorrelation on words and its applications: analysis of suffix trees by string-ruler approach. preprint, 1990."},{"key":"12_CR17","unstructured":"C. J. A. Jansen. Investigations on Nonlinear Streamcipher systems: Construction and Evaluation methods. PhD thesis, Philips, USFA BV, 1989."},{"key":"12_CR18","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/0-387-34805-0_10","volume-title":"Advances in Cryptology, CRYPTO 89","author":"C. J. A. Jansen","year":"1990","unstructured":"C. J. A. Jansen and D. Boekee. The shortest feedbck shift register that can generate a sequence. Advances in Cryptology, CRYPTO 89, Lecture Notes in Computer Science, vol. 218, G. Brassard, ed., Springer-Verlag, pages 90\u201399, 1990."},{"issue":"6","key":"12_CR19","doi-asserted-by":"publisher","first-page":"732","DOI":"10.1109\/TIT.1976.1055626","volume":"22","author":"E. L. Key","year":"1976","unstructured":"E. L. Key. An analysis of the structure and complexity of nonlinear binary sequence generators. IEEE Transactions on Information Theory, 22(6):732\u2013736, 1976.","journal-title":"IEEE Transactions on Information Theory"},{"key":"12_CR20","unstructured":"D. E. Knuth. The Art of Computer Programming: Volume 3, Sorting and Searching. Addsion Wesley, 1973."},{"key":"12_CR21","unstructured":"D. E. Knuth. The Art of Computer Programming: Volume 2, Seminumerical Algorithms. Addsion Wesley, 1981."},{"issue":"1","key":"12_CR22","first-page":"1","volume":"1","author":"A. N. Kolmogorov","year":"1965","unstructured":"A. N. Kolmogorov. Three approaches to the quantitative definition of definition. Problems in Information Transmission, 1(1):1\u20137, 1965.","journal-title":"Problems in Information Transmission"},{"key":"12_CR23","unstructured":"M. Li and P. M. B. Vitanyi. Two decades of applied Kolmogorov complexity. Technical Report CS-R8813, Centre for Mathematics and Computer Science, April, 1988."},{"key":"12_CR24","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1109\/TIT.1969.1054260","volume":"15","author":"J. L. Massey","year":"1969","unstructured":"J. L. Massey. Shift-register synthesis and BCH decoding. IEEE Transactions on Information Theory, 15:122\u2013127, 1969.","journal-title":"IEEE Transactions on Information Theory"},{"key":"12_CR25","unstructured":"U. M Maurer. Asymptotically tight bounds on the number of cycles in generalized de Bruijn-Good graphs. to appear in Discrete Applied Mathematics."},{"issue":"2","key":"12_CR26","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"},{"issue":"2","key":"12_CR27","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/0020-0190(81)90033-8","volume":"13","author":"M. Regnier","year":"1981","unstructured":"M. Regnier. On the average height of trees in digital search and dynamic hashing. Information Processing Letters, 13(2):64\u201366, 1981.","journal-title":"Information Processing Letters"},{"key":"12_CR28","doi-asserted-by":"crossref","unstructured":"R. A. Rueppel. Design and Analysis of Stream Ciphers. Springer-Verlag, 1986.","DOI":"10.1007\/978-3-642-82865-2"},{"key":"12_CR29","unstructured":"J. Savage. The Complexity of Computing. John Wiley, 1976."},{"key":"12_CR30","unstructured":"W. Szpankowski. On the analysis of the average height of a digital search tree: another approach. Technical Report CSD-TR-646, Purdue University, 1986."}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2014 EUROCRYPT\u2019 92"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-47555-9_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:13:52Z","timestamp":1605647632000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-47555-9_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540564133"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-47555-9_12","relation":{},"subject":[]}}