{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:32:39Z","timestamp":1755999159467},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,1,18]],"date-time":"2014-01-18T00:00:00Z","timestamp":1390003200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,6]]},"DOI":"10.1007\/s00453-013-9860-6","type":"journal-article","created":{"date-parts":[[2014,1,17]],"date-time":"2014-01-17T15:55:37Z","timestamp":1389974137000},"page":"450-466","source":"Crossref","is-referenced-by-count":7,"title":["Suffix Trays and Suffix Trists: Structures for Faster Text Indexing"],"prefix":"10.1007","volume":"72","author":[{"given":"Richard","family":"Cole","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tsvi","family":"Kopelowitz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moshe","family":"Lewenstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,1,18]]},"reference":[{"issue":"1","key":"9860_CR1","doi-asserted-by":"crossref","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.\u00a0Discrete Algorithms 2(1), 53\u201386 (2004)","journal-title":"J.\u00a0Discrete Algorithms"},{"key":"9860_CR2","volume-title":"The Design and Analysis of Computer Algorithms","author":"A.V. Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, New York (1974)"},{"key":"9860_CR3","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/11575832_9","volume-title":"Proc. of Symp. on String Processing and Information Retrieval (SPIRE)","author":"A. Amir","year":"2005","unstructured":"Amir, A., Kopelowitz, T., Lewenstein, M., Lewenstein, N.: Towards real-time suffix tree construction. In: Proc. of Symp. on String Processing and Information Retrieval (SPIRE), pp. 67\u201378 (2005)"},{"key":"9860_CR4","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/j.jda.2012.07.003","volume":"18","author":"D. Breslauer","year":"2013","unstructured":"Breslauer, D., Italiano, G.F.: Near real-time suffix tree construction via the fringe marked ancestor problem. J. Discrete Algorithms 18, 32\u201348 (2013)","journal-title":"J. Discrete Algorithms"},{"key":"9860_CR5","first-page":"851","volume-title":"Proc. of the Symposium on Discrete Algorithms (SODA)","author":"R. Cole","year":"2003","unstructured":"Cole, R., Lewenstein, M.: Multidimensional matching and fast search in suffix trees. In: Proc. of the Symposium on Discrete Algorithms (SODA), pp. 851\u2013852 (2003)"},{"key":"9860_CR6","first-page":"365","volume-title":"Proc. of Symposium on Theory of Computing (STOC)","author":"P.F. Dietz","year":"1987","unstructured":"Dietz, P.F., Sleator, D.D.: Two algorithms for maintaining order in a list. In: Proc. of Symposium on Theory of Computing (STOC), pp. 365\u2013372 (1987)"},{"issue":"6","key":"9860_CR7","doi-asserted-by":"crossref","first-page":"987","DOI":"10.1145\/355541.355547","volume":"47","author":"M. Farach-Colton","year":"2000","unstructured":"Farach-Colton, M., Ferragina, P., Muthukrishnan, S.: On the sorting-complexity of suffix tree construction. J. ACM 47(6), 987\u20131011 (2000)","journal-title":"J. ACM"},{"key":"9860_CR8","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1007\/978-3-540-27836-8_52","volume-title":"Proc. 31st Intl. Col. on Automata, Languages and Programming (ICALP)","author":"G. Franceschini","year":"2004","unstructured":"Franceschini, G., Grossi, R.: A general technique for managing strings in comparison-driven data structures. In: Proc. 31st Intl. Col. on Automata, Languages and Programming (ICALP). LNCS, vol.\u00a03142, pp. 606\u2013617 (2004)"},{"key":"9860_CR9","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1007\/3-540-48523-6_34","volume-title":"Proc. of the Intl. Col. on Automata, Languages and Programming (ICALP)","author":"R. Grossi","year":"1999","unstructured":"Grossi, R., Italiano, G.F.: Efficient techniques for maintaining multidimensional keys in linked data structures. In: Proc. of the Intl. Col. on Automata, Languages and Programming (ICALP), pp. 372\u2013381 (1999)"},{"issue":"6","key":"9860_CR10","doi-asserted-by":"crossref","first-page":"918","DOI":"10.1145\/1217856.1217858","volume":"53","author":"J. K\u00e4rkk\u00e4inen","year":"2006","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P., Burkhardt, S.: Linear work suffix array construction. J. ACM 53(6), 918\u2013936 (2006)","journal-title":"J. ACM"},{"issue":"2\u20134","key":"9860_CR11","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/j.jda.2004.08.019","volume":"3","author":"D.K. Kim","year":"2005","unstructured":"Kim, D.K., Sim, J.S., Park, H., Park, K.: Constructing suffix arrays in linear time. J. Discrete Algorithms 3(2\u20134), 126\u2013142 (2005)","journal-title":"J. Discrete Algorithms"},{"issue":"2\u20134","key":"9860_CR12","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/j.jda.2004.08.002","volume":"3","author":"P. Ko","year":"2005","unstructured":"Ko, P., Aluru, S.: Space efficient linear time construction of suffix arrays. J. Discrete Algorithms 3(2\u20134), 143\u2013156 (2005)","journal-title":"J. Discrete Algorithms"},{"key":"9860_CR13","first-page":"283","volume-title":"Proc. of the Symposium on Foundations of Computer Science (FOCS)","author":"T. Kopelowitz","year":"2012","unstructured":"Kopelowitz, T.: On-line indexing for general alphabets via predecessor queries on subsets of an ordered list. In: Proc. of the Symposium on Foundations of Computer Science (FOCS), pp. 283\u2013292 (2012)"},{"key":"9860_CR14","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/978-3-642-40273-9_18","volume-title":"Space-Efficient Data Structures, Streams, and Algorithms","author":"M. Lewenstein","year":"2013","unstructured":"Lewenstein, M.: Orthogonal range searching for text indexing. In: Space-Efficient Data Structures, Streams, and Algorithms. LNCS, vol. 8066, pp. 267\u2013302 (2013)"},{"issue":"5","key":"9860_CR15","doi-asserted-by":"crossref","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. 22(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"key":"9860_CR16","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"E.M. McCreight","year":"1976","unstructured":"McCreight, E.M.: A space-economical suffix tree construction algorithm. J. ACM 23, 262\u2013272 (1976)","journal-title":"J. ACM"},{"key":"9860_CR17","series-title":"EATCS Monographs in Theoretical Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69672-5","volume-title":"Data Structures and Algorithms 1: Sorting and Searching","author":"K. Mehlhorn","year":"1984","unstructured":"Mehlhorn, K.: Data Structures and Algorithms 1: Sorting and Searching. EATCS Monographs in Theoretical Computer Science. Spriger, Berlin (1984)"},{"key":"9860_CR18","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1007\/978-3-540-70575-8_8","volume-title":"Proc. of the Intl. Col. on Automata, Languages and Programming (ICALP)","author":"M. Ruzic","year":"2008","unstructured":"Ruzic, M.: Constructing efficient dictionaries in close to sorting time. In: Proc. of the Intl. Col. on Automata, Languages and Programming (ICALP), vol. 1, pp. 84\u201395 (2008)"},{"key":"9860_CR19","series-title":"CBMS-NSF Regional Conference Series in Applied Mathematics","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R.E. Tarjan","year":"1983","unstructured":"Tarjan, R.E.: Data Structures and Network Algorithms. CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 44. SIAM, Philadelphia (1983)"},{"key":"9860_CR20","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/BF01206331","volume":"14","author":"E. Ukkonen","year":"1995","unstructured":"Ukkonen, E.: On-line construction of suffix trees. Algorithmica 14, 249\u2013260 (1995)","journal-title":"Algorithmica"},{"key":"9860_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/SWAT.1973.13","volume-title":"Proc. 14th IEEE Symposium on Switching and Automata Theory","author":"P. Weiner","year":"1973","unstructured":"Weiner, P.: Linear pattern matching algorithm. In: Proc. 14th IEEE Symposium on Switching and Automata Theory, pp. 1\u201311 (1973)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9860-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9860-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9860-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:13Z","timestamp":1559137513000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9860-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1,18]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,6]]}},"alternative-id":["9860"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9860-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1,18]]}}}