{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T00:10:18Z","timestamp":1742947818649,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642245824"},{"type":"electronic","value":"9783642245831"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-24583-1_30","type":"book-chapter","created":{"date-parts":[[2011,9,30]],"date-time":"2011-09-30T13:08:23Z","timestamp":1317388103000},"page":"301-312","source":"Crossref","is-referenced-by-count":2,"title":["On Suffix Extensions in Suffix Trees"],"prefix":"10.1007","author":[{"given":"Dany","family":"Breslauer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"30_CR1","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1006\/inco.1995.1090","volume":"119","author":"A. Amir","year":"1995","unstructured":"Amir, A., Farach, M., Idury, R., Poutr\u00e9, J.L., Sch\u00e4ffer, A.: Improved Dynamic Dictionary-Matching. Information and Computation\u00a0119, 258\u2013282 (1995)","journal-title":"Information and Computation"},{"key":"30_CR2","series-title":"NATO ASI Series F","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-3-642-82456-2_6","volume-title":"Combinatorial Algorithms on Words","author":"A. Apostolico","year":"1985","unstructured":"Apostolico, A.: The Myriad Virtues of Subword Trees. In: Apostolico, A., Galil, Z. (eds.) Combinatorial Algorithms on Words. NATO ASI Series F, vol.\u00a012, pp. 85\u201396. Springer, Berlin (1985)"},{"key":"30_CR3","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0304-3975(83)90109-3","volume":"22","author":"A. Apostolico","year":"1983","unstructured":"Apostolico, A., Preparata, F.: Optimal Off-line Detection of Repetitions in a String. Theoret. Comput. Sci.\u00a022, 297\u2013315 (1983)","journal-title":"Theoret. Comput. Sci."},{"key":"30_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/3-540-45749-6_17","volume-title":"Algorithms - ESA 2002","author":"M.A. Bender","year":"2002","unstructured":"Bender, M.A., Cole, R., Demaine, E.D., Farach-Colton, M., Zito, J.: Two Simplified Algorithms for Maintaining Order in a List. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 152\u2013164. Springer, Heidelberg (2002)"},{"key":"30_CR5","doi-asserted-by":"crossref","unstructured":"Berstel, J.: Transductions and Context-Free Languages. Teubner-Verlag (1979) Revised version is available electronically as, http:\/\/www-igm.univ-mlv.fr~berstel\/LivreTransductions\/LivreTransductions14dec2009.pdf","DOI":"10.1007\/978-3-663-09367-1_2"},{"issue":"1","key":"30_CR6","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1142\/S0129626496000054","volume":"6","author":"D. Breslauer","year":"1996","unstructured":"Breslauer, D., Hariharan, R.: Optimal Parallel Construction of Minimal Suffix and Factor Automata. Parallel Processing Letters\u00a06(1), 35\u201344 (1996)","journal-title":"Parallel Processing Letters"},{"key":"30_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1044","DOI":"10.1007\/978-3-642-10631-6_105","volume-title":"Algorithms and Computation","author":"H. Cohen","year":"2009","unstructured":"Cohen, H., Porat, E.: Range Non-overlapping Indexing. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol.\u00a05878, pp. 1044\u20131053. Springer, Heidelberg (2009)"},{"key":"30_CR8","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0304-3975(86)90041-1","volume":"12","author":"M. Crochemore","year":"1986","unstructured":"Crochemore, M.: Transducers and Repetitions. Theoret. Comput. Sci.\u00a012, 63\u201386 (1986)","journal-title":"Theoret. Comput. Sci."},{"key":"30_CR9","volume-title":"Text Algorithms","author":"M. Crochemore","year":"1994","unstructured":"Crochemore, M., Rytter, W.: Text Algorithms. Oxford University Press, Oxford (1994)"},{"key":"30_CR10","first-page":"365","volume-title":"STOC","author":"P.F. Dietz","year":"1987","unstructured":"Dietz, P.F., Sleator, D.D.: Two Algorithms for Maintaining Order in a List. In: STOC, pp. 365\u2013372. ACM, New York (1987)"},{"issue":"2","key":"30_CR11","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.ipl.2005.11.019","volume":"98","author":"S. Dori","year":"2006","unstructured":"Dori, S., Landau, G.M.: Construction of Aho Corasick Automaton in Linear Time for Integer Alphabets. Inf. Process. Lett.\u00a098(2), 66\u201372 (2006)","journal-title":"Inf. Process. Lett."},{"key":"30_CR12","doi-asserted-by":"crossref","unstructured":"Farach, M.: Optimal Suffix Tree Construction with Large Alphabets. In: FOCS, pp. 137\u2013143 (1997)","DOI":"10.1109\/SFCS.1997.646102"},{"issue":"6","key":"30_CR13","doi-asserted-by":"publisher","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 Cree construction. J. ACM\u00a047(6), 987\u20131011 (2000)","journal-title":"J. ACM"},{"key":"30_CR14","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1090\/S0002-9939-1965-0174934-9","volume":"16","author":"N. Fine","year":"1965","unstructured":"Fine, N., Wilf, H.: Uniqueness Theorems for Periodic Functions. Proc. Amer. Math. Soc.\u00a016, 109\u2013114 (1965)","journal-title":"Proc. Amer. Math. Soc."},{"issue":"3","key":"30_CR15","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/PL00009177","volume":"19","author":"R. Giegerich","year":"1997","unstructured":"Giegerich, R., Kurtz, S.: From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction. Algorithmica\u00a019(3), 331\u2013353 (1997)","journal-title":"Algorithmica"},{"key":"30_CR16","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology","author":"D. Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)"},{"issue":"4","key":"30_CR17","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1016\/j.jcss.2004.03.004","volume":"69","author":"D. Gusfield","year":"2004","unstructured":"Gusfield, D., Stoye, J.: Linear Time Algorithms for Finding and Representing all the Tandem Repeats in a String. J. Comput. Syst. Sci.\u00a069(4), 525\u2013546 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"30_CR18","doi-asserted-by":"publisher","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\u00a053(6), 918\u2013936 (2006)","journal-title":"J. ACM"},{"issue":"2-4","key":"30_CR19","doi-asserted-by":"publisher","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\u00a03(2-4), 126\u2013142 (2005)","journal-title":"J. Discrete Algorithms"},{"issue":"2-4","key":"30_CR20","doi-asserted-by":"publisher","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\u00a03(2-4), 143\u2013156 (2005)","journal-title":"J. Discrete Algorithms"},{"key":"30_CR21","doi-asserted-by":"crossref","unstructured":"Kolpakov, R.M., Kucherov, G.: Finding Maximal Repetitions in a Word in Linear Time. In: FOCS, pp. 596\u2013604 (1999)","DOI":"10.1109\/SFFCS.1999.814634"},{"key":"30_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/3-540-58094-8_13","volume-title":"Combinatorial Pattern Matching","author":"S. Kosaraju","year":"1994","unstructured":"Kosaraju, S.: Computation of Squares in a String. In: Crochemore, M., Gusfield, D. (eds.) CPM 1994. LNCS, vol.\u00a0807, pp. 146\u2013150. Springer, Heidelberg (1994)"},{"issue":"5","key":"30_CR23","doi-asserted-by":"publisher","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.\u00a022(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"key":"30_CR24","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"E. McCreight","year":"1976","unstructured":"McCreight, E.: A Space Economical Suffix Tree Construction Algorithm. J. Assoc. Comput. Mach.\u00a023, 262\u2013272 (1976)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"43","key":"30_CR25","doi-asserted-by":"publisher","first-page":"4350","DOI":"10.1016\/j.tcs.2009.07.016","volume":"410","author":"M. Salson","year":"2009","unstructured":"Salson, M., Lecroq, T., L\u00e9onard, M., Mouchard, L.: A Four-Stage Algorithm for Updating a Burrows-Wheeler Transform. Theor. Comput. Sci.\u00a0410(43), 4350\u20134359 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"30_CR26","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/j.jda.2009.02.007","volume":"8","author":"M. Salson","year":"2010","unstructured":"Salson, M., Lecroq, T., L\u00e9onard, M., Mouchard, L.: Dynamic Extended Suffix Arrays. J. Discrete Algorithms\u00a08(2), 241\u2013257 (2010)","journal-title":"J. Discrete Algorithms"},{"key":"30_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/3-540-46632-0_24","volume-title":"Algorithms and Computations","author":"T. Shibuya","year":"1999","unstructured":"Shibuya, T.: Constructing the Suffix Tree of a Tree with a Large Alphabet. In: Aggarwal, A.K., Pandu Rangan, C. (eds.) ISAAC 1999. LNCS, vol.\u00a01741, pp. 225\u2013236. Springer, Heidelberg (1999)"},{"key":"30_CR28","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF00289142","volume":"21","author":"A.K. Tsakalidis","year":"1984","unstructured":"Tsakalidis, A.K.: Maintaining Order in a Generalized Linked List. Acta Inf.\u00a021, 101\u2013112 (1984)","journal-title":"Acta Inf."},{"issue":"3","key":"30_CR29","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01206331","volume":"14","author":"E. Ukkonen","year":"1995","unstructured":"Ukkonen, E.: On-line Construction of Suffix Trees. Algorithmica\u00a014(3), 249\u2013260 (1995)","journal-title":"Algorithmica"},{"key":"30_CR30","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear Pattern Matching Algorithms. In: Proc. 14th Symposium on Switching and Automata Theory, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"},{"key":"30_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/3-540-55719-9_86","volume-title":"Automata, Languages and Programming","author":"J. Westbrook","year":"1992","unstructured":"Westbrook, J.: Fast Incremental Planarity Testing. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol.\u00a0623, pp. 342\u2013353. Springer, Heidelberg (1992)"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-24583-1_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,16]],"date-time":"2019-06-16T16:31:45Z","timestamp":1560702705000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-24583-1_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642245824","9783642245831"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-24583-1_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}