{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T18:29:43Z","timestamp":1743100183385,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"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_16","type":"book-chapter","created":{"date-parts":[[2011,9,30]],"date-time":"2011-09-30T13:08:23Z","timestamp":1317388103000},"page":"156-167","source":"Crossref","is-referenced-by-count":4,"title":["Near Real-Time Suffix Tree Construction via the Fringe Marked Ancestor Problem"],"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":"16_CR1","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Husfeldt, T., Rauhe, T.: Marked ancestor problems. In: FOCS, pp. 534\u2013544 (1998)","DOI":"10.1109\/SFCS.1998.743504"},{"key":"16_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/11575832_9","volume-title":"String Processing and Information Retrieval","author":"A. Amir","year":"2005","unstructured":"Amir, A., Kopelowitz, T., Lewenstein, M., Lewenstein, N.: Towards real-time suffix tree construction. In: Consens, M.P., Navarro, G. (eds.) SPIRE 2005. LNCS, vol.\u00a03772, pp. 67\u201378. Springer, Heidelberg (2005)"},{"key":"16_CR3","first-page":"1086","volume-title":"SODA","author":"A. Amir","year":"2008","unstructured":"Amir, A., Nor, I.: Real-time indexing over fixed finite alphabets. In: Teng, S.H. (ed.) SODA, pp. 1086\u20131095. SIAM, Philadelphia (2008)"},{"issue":"3","key":"16_CR4","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1145\/28869.28873","volume":"34","author":"A. Blumer","year":"1987","unstructured":"Blumer, A., Blumer, J., Haussler, D., McConnel, R., Ehrenfeucht, A.: Complete inverted files for efficient text retrieval and analysis. J. Assoc. Comput. Mach.\u00a034(3), 578\u2013595 (1987)","journal-title":"J. Assoc. Comput. Mach."},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"Breslauer, D., Italiano, G.F.: On Suffix Extensions in Suffix Trees (2011), this conference proceedings","DOI":"10.1007\/978-3-642-24583-1_30"},{"issue":"1-2","key":"16_CR6","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/S0304-3975(96)00319-2","volume":"191","author":"D. Breslauer","year":"1998","unstructured":"Breslauer, D.: The Suffix Tree of a Tree and Minimizing Sequential Transducers. Theor. Comput. Sci.\u00a0191(1-2), 131\u2013144 (1998)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"16_CR7","doi-asserted-by":"publisher","first-page":"894","DOI":"10.1137\/S0097539700370539","volume":"34","author":"R. Cole","year":"2005","unstructured":"Cole, R., Hariharan, R.: Dynamic LCA Queries on Trees. SIAM J. Comput.\u00a034(4), 894\u2013923 (2005)","journal-title":"SIAM J. Comput."},{"key":"16_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":"16_CR9","volume-title":"Text Algorithms","author":"M. Crochemore","year":"1994","unstructured":"Crochemore, M., Rytter, W.: Text Algorithms. Oxford University Press, Oxford (1994)"},{"key":"16_CR10","unstructured":"Dietz, P.F., Raman, R.: Persistence, amortization and randomization. In: SODA, pp. 78\u201388 (1991)"},{"key":"16_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1007\/978-3-540-27836-8_52","volume-title":"Automata, Languages and Programming","author":"G. Franceschini","year":"2004","unstructured":"Franceschini, G., Grossi, R.: A general technique for managing strings in comparison-driven data structures. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 606\u2013617. Springer, Heidelberg (2004)"},{"key":"16_CR12","series-title":"NATO ASI Series F","first-page":"1","volume-title":"Combinatorial Algorithms on Words","author":"Z. Galil","year":"1984","unstructured":"Galil, Z.: Open problems in stringology. In: Apostolico, A., Galil, Z. (eds.) Combinatorial Algorithms on Words. NATO ASI Series F, vol.\u00a012, pp. 1\u20138. Springer, Berlin (1984)"},{"key":"16_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1007\/3-540-48523-6_34","volume-title":"Automata, Languages and Programming","author":"R. Grossi","year":"1999","unstructured":"Grossi, R., Italiano, G.F.: Efficient techniques for maintaining multidimensional keys in linked data structures. In: Wiedermann, J., Van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol.\u00a01644, pp. 372\u2013381. Springer, Heidelberg (1999)"},{"key":"16_CR14","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":"1","key":"16_CR15","first-page":"52","volume":"10","author":"S. Inenaga","year":"2003","unstructured":"Inenaga, S.: Bidirectional construction of suffix trees. Nord. J. Comput.\u00a010(1), 52\u201367 (2003)","journal-title":"Nord. J. Comput."},{"key":"16_CR16","unstructured":"Kopelowitz, T.: From Off-line to On-line Indexing Data-Structures. Ph.D. thesis, Dept. of Computer Science, Bar-Ilan University (2011)"},{"key":"16_CR17","doi-asserted-by":"crossref","unstructured":"Kosaraju, S.R.: Real-time pattern matching and quasi-real-time construction of suffix trees (preliminary version). In: STOC, pp. 310\u2013316 (1994)","DOI":"10.1145\/195058.195170"},{"issue":"1","key":"16_CR18","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s00453-003-1029-2","volume":"37","author":"M.G. Maa\u00df","year":"2003","unstructured":"Maa\u00df, M.G.: Linear bidirectional on-line construction of affix trees. Algorithmica\u00a037(1), 43\u201374 (2003)","journal-title":"Algorithmica"},{"issue":"5","key":"16_CR19","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":"16_CR20","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."},{"key":"16_CR21","unstructured":"Seiferas, J.: Subword Trees (undated manuscript)"},{"key":"16_CR22","doi-asserted-by":"crossref","unstructured":"Slisenko, A.: Detection of periodicities and string-matching in real time. J. of Soviet Mathematics, 1316\u20131386 (1983)","DOI":"10.1007\/BF01084395"},{"key":"16_CR23","unstructured":"Stoye, J.: Affix Trees. Master\u2019s thesis, Technische Fakultat, Universitat Bielefeld, Bielefeld, Germany (2000), report 2000-04"},{"issue":"3","key":"16_CR24","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":"16_CR25","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"}],"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_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,16]],"date-time":"2019-06-16T16:32:04Z","timestamp":1560702724000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-24583-1_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642245824","9783642245831"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-24583-1_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}