{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T19:38:20Z","timestamp":1794339500263,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540584346","type":"print"},{"value":"9783540487944","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/bfb0049434","type":"book-chapter","created":{"date-parts":[[2006,3,6]],"date-time":"2006-03-06T13:42:35Z","timestamp":1141652555000},"page":"495-507","source":"Crossref","is-referenced-by-count":3,"title":["Incremental text editing: a new data structure"],"prefix":"10.1007","author":[{"given":"Paolo","family":"Ferragina","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2006,2,23]]},"reference":[{"key":"44_CR1","first-page":"255","volume-title":"Handbook of Theoretical Computer Science","author":"A. V. Aho","year":"1990","unstructured":"A. V. Aho. Algorithms for finding patterns in strings, chapter A, 255\u2013300. Handbook of Theoretical Computer Science. MIT press, Cambridge, 1990."},{"key":"44_CR2","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The design and analysis of computer algorithms. Addison-Wesley, 1974."},{"key":"44_CR3","doi-asserted-by":"crossref","unstructured":"A. Amir, M. Farach. Adaptive dictionary matching. Proc. of IEEE Symposium on Foundations of Computer Science, 760\u2013766, 1991.","DOI":"10.1109\/SFCS.1991.185445"},{"key":"44_CR4","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/BF01762122","volume":"3","author":"A. Apostolico","year":"1988","unstructured":"A. Apostolico, C. Iliopolus, G. M. Landau, B. Schieber, and U. Vishkin. Parallel construction of a suffix tree with applications. Algorithmica, 3:347\u2013365, 1988.","journal-title":"Algorithmica"},{"key":"44_CR5","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1145\/359842.359859","volume":"20","author":"R. S. Boyer","year":"1977","unstructured":"R. S. Boyer and J. S. Moore. A fast string searching algorithm. Communications of the ACM, 20:762\u2013772, 1977.","journal-title":"Communications of the ACM"},{"key":"44_CR6","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1137\/0215051","volume":"15","author":"B. M. Chazelle","year":"1986","unstructured":"B. M. Chazelle. Filtering search: a new approach to query answering. SIAM Journal of Computing, 15:703\u2013724, 1986.","journal-title":"SIAM Journal of Computing"},{"key":"44_CR7","doi-asserted-by":"crossref","unstructured":"M. T. Chen and J. Seiferas. Efficient and elegant subword tree construction. Combinatorial algorithms in word, 97\u2013107. Springer-Verlag, 1985.","DOI":"10.1007\/978-3-642-82456-2_7"},{"key":"44_CR8","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1016\/S0019-9958(85)80031-0","volume":"67","author":"Z. Galil","year":"1985","unstructured":"Z. Galil. Optimal parallel algorithms for string matching. Information and Control, 67:144\u2013157, 1985.","journal-title":"Information and Control"},{"key":"44_CR9","unstructured":"M. Gu, M. Farach, and R. Beigel. An efficient algorithm for dynamic text editing. ACM-SIAM Symposium on Discrete Algorithms, 1994."},{"key":"44_CR10","doi-asserted-by":"crossref","unstructured":"R. Grossi, F. Luccio, and L. Pagli. Coding trees as strings for approximate tree matching, 245\u2013259. Sequences II: Methods in Communication, Security and Computer Science, 1992.","DOI":"10.1007\/978-1-4613-9323-8_18"},{"key":"44_CR11","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0020-0190(92)90176-V","volume":"41","author":"D. Gusfield","year":"1992","unstructured":"D. Gusfield, G. M. Landau, and B. Schieber. An efficient algorithm for all pairs suffix-prefix problem. Information Processing Letters, 41:181\u2013185, 1992.","journal-title":"Information Processing Letters"},{"key":"44_CR12","doi-asserted-by":"crossref","unstructured":"R. Hariharan. Optimal parallel suffix tree construction. ACM Symposium on Theory of Computing, 1994.","DOI":"10.1145\/195058.195162"},{"key":"44_CR13","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1145\/322290.322295","volume":"29","author":"C. M. Hoffmann","year":"1982","unstructured":"C. M. Hoffmann and M. J. O'Donnell. Pattern matching in trees. Journal of the ACM, 29:68\u201395, 1982.","journal-title":"Journal of the ACM"},{"key":"44_CR14","doi-asserted-by":"crossref","unstructured":"R. M. Karp and V. Ramachandran. A survey of parallel algorithms for shared memory machines, chapter 17, 869\u2013941. Handbook of Theoretical Computer Science. Elsevier Science Publisher B.V., j. van Leeuwen edition, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"44_CR15","doi-asserted-by":"crossref","unstructured":"R. Karp, R. Miller, and A. Rosenberg. Rapid identification of repeated patterns in strings, arrays and trees. In Proc. 4th Symposium on Theory of Computing, pages 125\u2013136. ACM, 1972.","DOI":"10.1145\/800152.804905"},{"key":"44_CR16","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1007\/BF00292114","volume":"24","author":"M. Kempf","year":"1987","unstructured":"M. Kempf, R. Bayer, and U. Guntzer. Time optimal left to right construction of position trees. Acta Informatica, 24:475\u2013489, 1987.","journal-title":"Acta Informatica"},{"issue":"2","key":"44_CR17","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1137\/0206024","volume":"6","author":"D. E. Knuth","year":"1977","unstructured":"D. E. Knuth, J. H. Morris, and V. R. Pratt. Fast pattern matching in strings. SIAM Journal of Computing, 6(2):63\u201378, 1977.","journal-title":"SIAM Journal of Computing"},{"key":"44_CR18","doi-asserted-by":"crossref","unstructured":"S.R. Kosaraju. Efficient tree pattern matching. Proc. IEEE Symposium on Foundations of Computer Science, 178\u2013183, 1989.","DOI":"10.1109\/SFCS.1989.63475"},{"key":"44_CR19","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/0020-0190(89)90056-2","volume":"32","author":"E. M\u00e4kinen","year":"1988","unstructured":"E. M\u00e4kinen. On the subtree isomorphism problem for ordered trees. Information Processing Letters, 32:271\u2013273, 1988.","journal-title":"Information Processing Letters"},{"issue":"2","key":"44_CR20","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"},{"key":"44_CR21","volume-title":"Technical Report A-1\/93","author":"E. Ukkonen","year":"1993","unstructured":"E. Ukkonen. On-line construction of suffix tree. Technical Report A-1\/93, Dept. of Computer Science, University of Helsinki, Finland, 1993."},{"key":"44_CR22","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1137\/0214019","volume":"14","author":"D. E. Willard","year":"1985","unstructured":"D. E. Willard. New data structures for orthogonal range queries. SIAM Journal of Computing, 14:232\u2013253, 1985.","journal-title":"SIAM Journal of Computing"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0049434","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,17]],"date-time":"2019-04-17T01:56:22Z","timestamp":1555466182000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0049434"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540584346","9783540487944"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/bfb0049434","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/bfb0049390","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994]]}}}