{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T08:33:55Z","timestamp":1790843635295,"version":"4.1.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2007,5,1]],"date-time":"2007-05-01T00:00:00Z","timestamp":1177977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2007,5]]},"abstract":"<jats:p>\n            In this article, we address a new version of dynamic pattern matching. The\n            <jats:italic>dynamic text and static pattern matching problem<\/jats:italic>\n            is the problem of finding a static pattern in a text that is continuously being updated. The goal is to report all new occurrences of the pattern in the text after each text update. We present an algorithm for solving the problem where the text update operation is\n            <jats:italic>changing<\/jats:italic>\n            the symbol value of a text location. Given a text of length\n            <jats:italic>n<\/jats:italic>\n            and a pattern of length\n            <jats:italic>m<\/jats:italic>\n            , our algorithm preprocesses the text in time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log log\n            <jats:italic>m<\/jats:italic>\n            ), and the pattern in time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            log\n            <jats:italic>m<\/jats:italic>\n            ). The extra space used is\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>m<\/jats:italic>\n            log\n            <jats:italic>m<\/jats:italic>\n            ). Following each text update, the algorithm deletes all prior occurrences of the pattern that no longer match, and reports all new occurrences of the pattern in the text in\n            <jats:italic>O<\/jats:italic>\n            (log log\n            <jats:italic>m<\/jats:italic>\n            ) time. We note that the complexity is not proportional to the number of pattern occurrences, since all new occurrences can be reported in a succinct form.\n          <\/jats:p>","DOI":"10.1145\/1240233.1240242","type":"journal-article","created":{"date-parts":[[2007,6,6]],"date-time":"2007-06-06T14:37:11Z","timestamp":1181140631000},"page":"19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":39,"title":["Dynamic text and static pattern matching"],"prefix":"10.1145","volume":"3","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[{"name":"Bar-Ilan University and Georgia Tech, Ramat-Gan, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gad M.","family":"Landau","sequence":"additional","affiliation":[{"name":"University of Haifa and Polytechnic University, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Moshe","family":"Lewenstein","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Ramat-Gan, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dina","family":"Sokol","sequence":"additional","affiliation":[{"name":"Brooklyn College of the City University of New York"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2007,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940874"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 819--828","author":"Alstrup S.","unstructured":"Alstrup , S. , Brodal , G. S. , and Rauhe , T . 2000. Pattern matching in dynamic texts . In Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 819--828 . Alstrup, S., Brodal, G. S., and Rauhe, T. 2000. Pattern matching in dynamic texts. In Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 819--828."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1822"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80002-9"},{"key":"e_1_2_1_5_1","unstructured":"Buchsbaum A. L. 2006. Personal communication.  Buchsbaum A. L. 2006. Personal communication."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 8th Annual European Symposium on Algorithms (ESA). Springer Verlag","author":"Buchsbaum A. L.","unstructured":"Buchsbaum , A. L. , Goodrich , M. T. , and Westbrook , J . 2000. Range searching over tree cross products . In Proceedings of the 8th Annual European Symposium on Algorithms (ESA). Springer Verlag , Berlin. 120--131. Buchsbaum, A. L., Goodrich, M. T., and Westbrook, J. 2000. Range searching over tree cross products. In Proceedings of the 8th Annual European Symposium on Algorithms (ESA). Springer Verlag, Berlin. 120--131."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979324694X"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/795663.796326"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 7th Symposium on Combinatorial Pattern Matching (CPM). Springer Verlag","author":"Farach M.","unstructured":"Farach , M. , and Muthukrishnan , S . 1996. Perfect hashing for strings: Formalization and algorithms . In Proceedings of the 7th Symposium on Combinatorial Pattern Matching (CPM). Springer Verlag , Berlin. 130--140. Farach, M., and Muthukrishnan, S. 1996. Perfect hashing for strings: Formalization and algorithms. In Proceedings of the 7th Symposium on Combinatorial Pattern Matching (CPM). Springer Verlag, Berlin. 130--140."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms (SODA). 531--540","author":"Ferragina P.","unstructured":"Ferragina , P. , and Grossi , R . 1995. Fast incremental text editing . In Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms (SODA). 531--540 . Ferragina, P., and Grossi, R. 1995. Fast incremental text editing. In Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms (SODA). 531--540."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808675"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms (SODA). 697--704","author":"Gu M.","unstructured":"Gu , M. , Farach , M. , and Beigel , R . 1994. An efficient algorithm for dynamic text indexing . In Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms (SODA). 697--704 . Gu, M., Farach, M., and Beigel, R. 1994. An efficient algorithm for dynamic text indexing. In Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms (SODA). 697--704."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1171"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science","volume":"2719","author":"K\u00e4rkk\u00e4inen J.","unstructured":"K\u00e4rkk\u00e4inen , J. , and Sanders , P . 2003. Simple linear work suffix array construction . In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science , vol. 2719 . Springer Verlag, Berlin. 943--955. K\u00e4rkk\u00e4inen, J., and Sanders, P. 2003. Simple linear work suffix array construction. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 2719. Springer Verlag, Berlin. 943--955."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206024"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90045-1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01185433"},{"key":"e_1_2_1_19_1","first-page":"707","article-title":"Binary codes capable of correcting, deletions, insertions and reversals","volume":"10","author":"Levenshtein V. I.","year":"1966","unstructured":"Levenshtein , V. I. 1966 . Binary codes capable of correcting, deletions, insertions and reversals . Soviet Phys. Dokl. 10 , 707 -- 710 . Levenshtein, V. I. 1966. Binary codes capable of correcting, deletions, insertions and reversals. Soviet Phys. Dokl. 10, 707--710.","journal-title":"Soviet Phys. Dokl."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321880"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321946"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 37th IEEE Symposium on Foundations of Computer Science (FOCS). 320--328","author":"Sahinalp S. C.","unstructured":"Sahinalp , S. C. , and Vishkin , U . 1996. Efficient approximate and dynamic matching of patterns using a labeling paradigm . In Proceedings of the 37th IEEE Symposium on Foundations of Computer Science (FOCS). 320--328 . Sahinalp, S. C., and Vishkin, U. 1996. Efficient approximate and dynamic matching of patterns using a labeling paradigm. In Proceedings of the 37th IEEE Symposium on Foundations of Computer Science (FOCS). 320--328."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217079"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(81)90087-5"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01206331"},{"key":"e_1_2_1_26_1","unstructured":"van Emde Boas P. 1974. An O(n log log n) online algorithm for the insert-extract min problem. Tech. Rep. TR 74-221 Cornell University Department of Computer Science.   van Emde Boas P. 1974. An O(n log log n) online algorithm for the insert-extract min problem. Tech. Rep. TR 74-221 Cornell University Department of Computer Science."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1973.13"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90075-3"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1240233.1240242","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1240233.1240242","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:52:08Z","timestamp":1750258328000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1240233.1240242"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,5]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,5]]}},"alternative-id":["10.1145\/1240233.1240242"],"URL":"https:\/\/doi.org\/10.1145\/1240233.1240242","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,5]]},"assertion":[{"value":"2007-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}