{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:11Z","timestamp":1787337491077,"version":"build-2736575974"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>This paper investigates the problem of searching on-line for the occurrences (occ) of an arbitrary pattern of length p in a text of length n subjected to some updates after its preprocessing. Each text update consists of inserting or deleting an arbitrary string of length y. We present the first dynamic algorithm that achieves optimal query time, i.e., $\\Theta(p+occ)$, sublinear time per update, i.e., $O(\\sqrt{n} + y)$, and optimal space, i.e., $\\Theta(n)$, in the worst case. As a result, our algorithm obtains the same query time and space usage of suffix trees [McCreight, J. Assoc. Comput. Mach., 23 (1976), pp. 262--272] while improving their O(n + y) update performance.<\/jats:p>","DOI":"10.1137\/s0097539795286119","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"713-736","source":"Crossref","is-referenced-by-count":12,"title":["Optimal On-Line Search and Sublinear Time Update in String Matching"],"prefix":"10.1137","volume":"27","author":[{"given":"Paolo","family":"Ferragina","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roberto","family":"Grossi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","unstructured":"A. Aho, D\u017e. Hopkroft, D\u017e. Ul\u2019man, Postroenie i analiz vychislitelnykh algoritmov, \u201cMir\u201d, 1979, 536\u20130, Translated by A. O. Slisenko; Edited by Ju. V. Matijasevi\u010d80g:68036"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80047-9"},{"key":"R3","unstructured":"Alberto Apostolico, The myriad virtues of subword trees, NATO Adv. Sci. Inst. Ser. F Comput. Systems Sci., Vol. 12, Springer, Berlin, 1985, 85\u201396815333"},{"key":"R4","unstructured":"R. A. Baeza\u2010Yates, and G. H. Gonnet,\n                      Handbook of Algorithms and Data Structures\n                      , Addison\u2010Wesley, Reading, MA, 1991."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0003"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90157-4"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28873"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01185431"},{"key":"R9","unstructured":"M. Chen, Joel Seiferas, Efficient and elegant subword\u2010tree construction, NATO Adv. Sci. Inst. Ser. F Comput. Systems Sci., Vol. 12, Springer, Berlin, 1985, 97\u201310787e:68034"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90041-1"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90060-B"},{"key":"R12","unstructured":"D. Eppstein, Z. Galil, G. F. Italiano, and A. Nissenzweig,\n                      Sparsification \u2010 A technique for speeding up dynamic graph algorithms\n                      , in Proc. IEEE Symposium on Foundations of Computer Science, IEEE, Piscataway, NJ, 1992, pp. 60\u201369."},{"key":"R13","unstructured":"P. Ferragina,\n                      Incremental text editing: A new data structure\n                      , in Proc. European Symposium on Algorithms, Lecture Notes in Computer Science 855, 1994, pp. 495\u2013507;"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0814"},{"key":"R14","unstructured":"Paolo Ferragina, Roberto Grossi, Fast incremental text editing, ACM, New York, 1995, 531\u201354096e:68142"},{"key":"R15","unstructured":"P. Ferragina and R. Grossi,\n                      A fully\u2010dynamic data structure for external substring search\n                      , in Proc. ACM Symposium on Theory of Computing, ACM, New York, 1995, pp. 693\u2013702."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(88)90008-8"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792231982"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0087"},{"key":"R19","unstructured":"G. H. Gonnet, R. A. Baeza\u2010Yates, and T. Snider,\n                      New indices for text: PAT trees and PAT arrays\n                      , in Information Retrieval: Data Structures and Algorithms, W. B. Frakes and R. A. Baeza\u2010Yates, eds., Prentice\u2010Hall, Englewood Cliffs, NJ, 1992, pp. 66\u201382."},{"key":"R20","unstructured":"M. Gu, M. Farach, and R. Beigel,\n                      An efficient algorithm for dynamic text indexing\n                      , in Proc. ACM\u2010SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 1994, pp. 697\u2013704."},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90176-V"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/BF00292114"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1137\/0206024"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90010-2"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/0209061"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321946"},{"key":"R29","volume-title":"The design of dynamic data structures","author":"Overmars Mark","year":"1983"},{"key":"R30","unstructured":"V. Pratt,\n                      Improvements and Applications for the Weiner Repetition Finder\n                      , manuscript, 1975."},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1137\/0217079"},{"key":"R32","unstructured":"F. N. Teskey,\n                      Principles of Text Processing\n                      , John Wiley, New York, 1983."},{"key":"R33","unstructured":"P. Weiner,\n                      Linear pattern matching algorithm\n                      , in Proc. IEEE Symposium on Switching and Automata Theory, IEEE, Piscataway, NJ, 1973, pp. 1\u201311."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539795286119","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:13:37Z","timestamp":1787336017000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539795286119"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539795286119"],"URL":"https:\/\/doi.org\/10.1137\/s0097539795286119","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}