{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T18:54:29Z","timestamp":1794336869158,"version":"4.9.0"},"publisher-location":"Berlin\/Heidelberg","reference-count":31,"publisher":"Springer-Verlag","isbn-type":[{"value":"3540543430","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0028265","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T00:52:14Z","timestamp":1132620734000},"page":"228-239","source":"Crossref","is-referenced-by-count":0,"title":["What can we learn about suffix trees from independent tries?"],"prefix":"10.1007","author":[{"given":"Philippe","family":"Jacquet","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wojciech","family":"Szpankowski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"22_CR1","doi-asserted-by":"crossref","unstructured":"A. Apostolico, The Myriad Virtues of Suffix Trees, Combinatorial Algorithms on Words, pp. 8596, Springer-Verlag, ASI F12 (1985).","DOI":"10.1007\/978-3-642-82456-2_6"},{"key":"22_CR2","unstructured":"A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley (1974)."},{"key":"#cr-split#-22_CR3.1","unstructured":"A. Apostolico, W. Szpankowski, Self-alignments in Words and Their Applications, Purdue CSD-TR-732 (1987);"},{"key":"#cr-split#-22_CR3.2","unstructured":"A. Apostolico, W. Szpankowski, Self-alignments in Words and Their Applications, Purdue CSD-TR-732 (1987); Journal of Algorithms, to appear."},{"key":"22_CR4","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0166-218X(92)90270-K","volume":"24","author":"A. Blumer","year":"1989","unstructured":"A. Blumer, A. Ehrenfeucht and D. Haussler, Average Size of Suffix Trees and DAWGS, Discrete Applied Mathematics, 24, 37\u201345 (1989).","journal-title":"Discrete Applied Mathematics"},{"key":"22_CR5","volume-title":"Random Graphs","author":"B. Bollob\u00e1s","year":"1985","unstructured":"B. Bollob\u00e1s Random Graphs, Academic Press, London (1985)."},{"key":"22_CR6","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/BF02279819","volume":"28","author":"L. Devroye","year":"1982","unstructured":"L. Devroye, A Note on the Average Depth of Tries, Computing, 28, 367\u2013371 (1982).","journal-title":"Computing"},{"key":"#cr-split#-22_CR7.1","unstructured":"L., Devroye, W. Szpankowski and B. Rais, A note of the height of suffix trees, Purdue University, CSD TR-905 (1989);"},{"key":"#cr-split#-22_CR7.2","unstructured":"L., Devroye, W. Szpankowski and B. Rais, A note of the height of suffix trees, Purdue University, CSD TR-905 (1989); SIAM J. Computing, to appear."},{"key":"22_CR8","doi-asserted-by":"crossref","first-page":"345369","DOI":"10.1007\/BF00264279","volume":"20","author":"P. Flajolet","year":"1983","unstructured":"P. Flajolet, On the Performance Evaluation of Extendible Hashing and Trie Searching, Acta Informatica, 20, 345369 (1983).","journal-title":"Acta Informatica"},{"key":"22_CR9","doi-asserted-by":"crossref","unstructured":"P. Flajolet, M. Regnier and R. Sedgewick, Some Uses of the Mellin Transform Techniques in the Analysis of Algorithms, in Combinatorial Algorithms on Words, Springer NATO ASI Ser. F12, 241\u2013254 (1985).","DOI":"10.1007\/978-3-642-82456-2_16"},{"key":"22_CR10","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1137\/0135034","volume":"35","author":"L. Guibas","year":"1978","unstructured":"L. Guibas and A. Odlyzko Maximal Prefix-Synchronized Codes, SIAM J. Appl. Math, 35, 401\u2013418 (1978).","journal-title":"SIAM J. Appl. Math"},{"key":"22_CR11","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0097-3165(81)90038-8","volume":"30","author":"L. Giubas","year":"1981","unstructured":"L. Giubas and A. Odlyzko, Periods in Strings Journal of Combinatorial Theory, Series A, 30, 19\u201343 (1981).","journal-title":"Journal of Combinatorial Theory"},{"key":"22_CR12","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0097-3165(81)90005-4","volume":"30","author":"L. Guibas","year":"1981","unstructured":"L. Guibas and A. W. Odlyzko, String Overlaps, Pattern Matching, and Nontransitive Games, Journal of Combinatorial Theory, Series A, 30, 183\u2013208 (1981).","journal-title":"Journal of Combinatorial Theory"},{"key":"22_CR13","unstructured":"P. Henrici, Applied and Computational Complex Analysis, John Wiley & Sons (1977)."},{"key":"22_CR14","first-page":"194","volume":"214","author":"P. Jacquet","year":"1986","unstructured":"P. Jacquet and M. Regnier, Trie Partitioning Process: Limiting Distribution, Proc. CAAP'86, Lecture Notes in Computer Science 214, 194\u2013210 (1986).","journal-title":"Lecture Notes in Computer Science"},{"key":"22_CR15","unstructured":"P. Jacquet and W. Szpankowski, Analysis of Tries With Markovian Dependency, Purdue University, CSD TR-906, 1989; IEEE Trans. Information Theory, to appear."},{"key":"22_CR16","unstructured":"P. Jacquet and W. Szpankowski, Autocorrelation on Words and Its Applications. Analysis of Suffix Trees by String-Ruler Approach, INRIA TR-1106, 1989."},{"key":"22_CR17","unstructured":"D. Knuth, The Art of Computer Programming. Sorting and Searching, Addison-Wesley (1973)."},{"key":"22_CR18","unstructured":"M. Lothaire, Combinatorics on Words, Addison-Wesley (1982)."},{"issue":"1","key":"22_CR19","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1109\/TIT.1976.1055501","volume":"22","author":"A. Lempel","year":"1976","unstructured":"A. Lempel and J. Ziv, On the Complexity of Finite Sequences, IEEE Information Theory 22, 1, 75\u201381 (1976).","journal-title":"IEEE Information Theory"},{"key":"22_CR20","doi-asserted-by":"crossref","unstructured":"E.M. McCreight, A Space Economical Suffix Tree Construction Algorithm, JACM, 23, 262272 (1976).","DOI":"10.1145\/321941.321946"},{"key":"22_CR21","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1214\/aop\/1176993000","volume":"18","author":"B. Pittel","year":"1985","unstructured":"B. Pittel, Asymptotic growth of a class of random trees, The Annals of Probability, 18, 414\u2013427 (1985).","journal-title":"The Annals of Probability"},{"key":"22_CR22","doi-asserted-by":"crossref","first-page":"139","DOI":"10.2307\/1427240","volume":"18","author":"B. Pittel","year":"1986","unstructured":"B. Pittel, Paths in a Random Digital Tree: Limiting Distributions, Adv. Appl. Prob., 18, 139\u2013155 (1986).","journal-title":"Adv. Appl. Prob."},{"key":"22_CR23","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1109\/18.42197","volume":"35","author":"M. Regnier","year":"1989","unstructured":"M. Regnier and P. Jacquet, New Results on the Size of Tries, IEEE Trans. Information Theory, 35, 203\u2013205 (1989).","journal-title":"IEEE Trans. Information Theory"},{"key":"22_CR24","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1145\/322234.322237","volume":"28","author":"M. Rodeh","year":"1981","unstructured":"M. Rodeh, V. Pratt and S. Even, Linear Algorithm for Data Compression via String Matching, Journal of the ACM, 28, 16\u201324 (1981).","journal-title":"Journal of the ACM"},{"key":"22_CR25","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1016\/0196-6774(88)90039-9","volume":"9","author":"W. Szpankowski","year":"1988","unstructured":"W. Szpankowski, Some Results on V-ary Asymmetric Tries, Journal of Algorithms, 9, 224\u2013244 (1988).","journal-title":"Journal of Algorithms"},{"key":"22_CR26","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/0020-0190(88)90137-8","volume":"28","author":"W. Szpankowski","year":"1988","unstructured":"W. Szpankowski, The Evaluation of an Alternating Sum with Applications to the Analysis of Some Data Structures, Information Processing Letters, 28, 13\u201319 (1988).","journal-title":"Information Processing Letters"},{"key":"22_CR27","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1007\/BF01759045","volume":"6","author":"W. Szpankowski","year":"1991","unstructured":"W. Szpankowski, On the Height of Digital Trees and Related Problems, Algorithmica, 6, 256\u2013277 (1991).","journal-title":"Algorithmica"},{"key":"22_CR28","doi-asserted-by":"crossref","unstructured":"P. Weiner, Linear Pattern Matching Algorithms, Proc. of the 14-th Annual Symposium on Switching and Automata Theory, 111 (1973).","DOI":"10.1109\/SWAT.1973.13"},{"issue":"3","key":"22_CR29","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"23","author":"J. Ziv","year":"1977","unstructured":"J. Ziv and A. Lempel, A Universal Algorithm for Sequential Data Compression, IEEE Information Theory, 23, 3, 337\u2013343 (1977).","journal-title":"IEEE Information Theory"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0028265","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,10]],"date-time":"2020-04-10T22:40:01Z","timestamp":1586558401000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0028265"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540543430"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/bfb0028265","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/bfb0028243","asserted-by":"object"}]},"subject":[]}}